Graphs: Adjacency Matrices — Visual Tour Behind the Scenes
In-Depth Look at the Logic and Code Behind Adjacency Matrices.
👋 Welcome!
Hi there! Graphs are extremely powerful data structures. They are used to represent a “network” of connected elements.
In this article, you will learn the logic behind Adjacency Matrices and how you can create them in Python to represent graphs. Let Begin! 😀🔮
1️⃣ Meet Adjacency Matrices
This is probably very similar to what you imagine when I mention the word “graph”, right?
It’s true, this diagram represents a graph, but don’t you think it’s too abstract to implement it in your code and in real-world scenarios?
1️⃣ What if your graph had thousands of nodes and connections?
2️⃣ How would you represent these connections in your code?
Don’t worry! Adjacency Matrices come to the rescue! 💥
They give us a way to represent our graph following a very efficient and structured procedure. By creating a matrix (a table with rows and columns), you can represent nodes and edges very easily.
Let’s see how you can create an Adjacency Matrix step by step! 👍
🔨 Let’s Create an Adjacency Matrix
We will create an Adjacency Table to represent this graph:
1️⃣ Draw Table to Represent the Nodes
As you can see in the diagram below, the rows and columns are used to represent the nodes in the graph. The graph has Nodes A, B, C, and D, so we include them all in the columns and rows. (Yes, repeated! 😊)
Continue reading to learn why we do this! 😉
2️⃣ Start Filling in the Blanks
Now it’s time to start representing the connections (edges) between the nodes. This is when you graph starts to come to life! 🔆
You can start filling in the blanks by row or by column. Depending on what you choose, you will need to analyze the graph differently. Let’s see how you can start analyzing it by rows:
Node A — Row:
If you start with the first row (Node A), you need to check if this Node has an edge directed towards each one of the nodes in the graph (including itself, which are called “loops”).
When you analyze by row, you need to ask yourself:
✅ Is there an edge from Node A to itself?
✅ Is there an edge from Node A to Node B?
✅ Is there an edge from Node A to Node C?
…. and so on. You can see the pattern. 👍
⚠️ If the answer to that question is “yes” for a pair of nodes, then you must write 1 in the cell that corresponds to the intersection between that pair of nodes.
Let’s see this in action! 😅
In the diagram below, you can see that the connections from Node A go towards Node B, Node C, and Node D, so you add 1 in the cells where A and B intersect, where A and C intersect, and where A and D intersect. Then, you fill the rest of the row with 0s, since there are no edges coming from Node A towards itself.
Node B—Row:
There are no edges coming out of this node, so you fill the entire row with zeros.
Node C— Row:
This node only has one edge coming out towards Node D, so you add 1 in the corresponding cell and complete the row with 0s.
Node D— Row:
Just like Node B, Node D has no edges going towards other nodes, so that entire row will be filled with zeros.
🏅 Voilà! — Our Matrix is Ready! Now Columns 👍
Awesome job! Now let’s see how you could fill this matrix column by column. You’ll see how we end up finding the exact same matrix.
To fill the table by columns, you must ask:
✅ What edges are coming towards Node A?
✅ What edges are coming towards Node B?
✅ What edges are coming towards Node C?
…. and so on. You can see the pattern. 👍
Node A — Column:
Since no edges are coming towards Node A, you fill the column with zeros.
Node B— Column:
The only edge coming towards Node B comes from Node A, so you write 1 in that cell and fill the rest of the column with zeros.
Node C— Column:
The only edge coming towards Node C comes from Node A, so you add 1 in that cell and fill the rest of the column with zeros.
Node D— Column:
There are two edges coming towards Node D, from Nodes A and C, so you add 1 in the corresponding cells and fill the rest of the column with zeros.
🏆 Finally! — Our Matrix is Ready! ❤️
You can see that the two matrices we obtained are equal, so both methods are equivalent. 🎉
💡 Note: Remember that undirected graphs have a two-way connection between connected pair of nodes, so that should be represented in the table as well. When there is an edge between Node A and Node B, there must be an edge between Node B and Node A.
🏋 Adjacency Matrices & Weighted Graphs
For weighted graphs, where each edge has a weight (value) associated with it, you simply replace the 1s with the weight of the edge, and 0s with Null because 0 can be a valid weight.
🚦 Use Cases
- Adjacency matrices should be used for dense graphs (graphs that have many edges).
- Otherwise, if the graph has very few edges, you would be wasting memory because the matrix will store many zeros due to the lack of connections. In this case, it’s recommended to use Adjacency lists (stay tuned for an article on this topic! 😄)
💻 To The Code!
The moment you’ve been waiting for has finally arrived! After learning what an Adjacency Matrix is, and the logic behind it, let’s dive into the code!
Here is an example of an unweighted directed graph represented with an Adjacency Matrix 👇
Let’s see how this code works behind the scenes: 🔍
1️⃣ Set up the Matrix
A 2D list, completely filled with zeros, is generated when you create an instance of the graph, thanks to this code:
def __init__(self, numNodes):
self.adjacencyMatrix = []
for i in range(numNodes):
self.adjacencyMatrix.append([0 for i in range(numNodes)])
self.numNodes = numNodesYour initial matrix would look like this (compare it with the diagram below):
self.adjacencyMatrix = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
2️⃣ Add Edges
Then, you start adding the edges. For example:
graph1 = Graph(4) # Create an instance of the graph with 4 nodes
graph1.addEdge(0, 1); # The 0th element is A. The 1st element is BThis will execute the method shown below, that assigns the value 1 to the corresponding cell:
def addEdge(self, start, end):
self.adjacencyMatrix[start][end] = 1On this line, self.adjacencyMatrix[start][end] = 1 :
- [start] selects the row.
- [end] selects the column.
- Finally, the value 1 is assigned at this position.
self.adjacencyMatrix = [[0, 1, 0, 0], # 0th row, 1st column.
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]At this point, our graph would look like the diagram below because we’ve only added the first edge.
We repeat the process until we’ve added all the edges and our graph looks like this:
3️⃣ Remove Edges
You can also remove edges from your graph. Let’s say that once you’ve set up your matrix, you want to remove the edge between Nodes C and D (shown below).
This method will check if there is an edge between the nodes and, if there is, it will remove it by setting the value to 0.
def removeEdge(self, start, end):
if self.adjacencyMatrix[start][end] == 0:
print("There is no edge between these nodes")
else:
self.adjacencyMatrix[start][end] = 0
4️⃣ Check if Two Nodes are Connected
You can also check if an edge exists by finding the element in the matrix and checking if it’s 0 or 1. If the value of the edge is greater than 0, an edge exists and the method returns True. Otherwise, there is no edge between these nodes and the method returns False.
def containsEdge(self, start, end):
if self.adjacencyMatrix[start][end] > 0:
return True
else:
return FalseLet’s say that you want to check if there is an edge between Nodes B and D.
You would call print(graph1.containsEdge(3, 1)) but since the value is 0, there is no edge between these nodes and False is returned.
If you liked this article, I suggest reading my article on Linked Lists:
📣 Stay tuned for a future article on Adjacent Lists, which are optimal for sparse graphs (graphs that don’t have many edges).
