PYTHON - ADJACENCY MATRIX CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Example :

def insertEdge(adjacentMatrix, i, j):
	adjacentMatrix[i][j] = True

def removeEdge(adjacentMatrix, i, j):
	adjacentMatrix[i][j] = False
        
def printAdjacencyMatrix(adjacentMatrix):
	for i in range(len(adjacentMatrix)):
		for j in range(len(adjacentMatrix[i])):
			val = 1 if adjacentMatrix[i][j] == True else 0
			print("|    ",val,"     |", end = ' ')
		print()

V = 5
         
adjacentMatrix = [[False for i in range(V)] for j in range(V)] 

#Insert Edges

insertEdge(adjacentMatrix, 0, 1)
insertEdge(adjacentMatrix, 0, 2)
insertEdge(adjacentMatrix, 0, 3)

insertEdge(adjacentMatrix, 1, 0)
insertEdge(adjacentMatrix, 1 ,4)

insertEdge(adjacentMatrix, 2, 0)
insertEdge(adjacentMatrix, 2, 3)
insertEdge(adjacentMatrix, 2, 4)

insertEdge(adjacentMatrix, 3, 0)
insertEdge(adjacentMatrix, 3 ,2)
insertEdge(adjacentMatrix, 3, 4)

insertEdge(adjacentMatrix, 4, 3)
insertEdge(adjacentMatrix, 4, 2)
insertEdge(adjacentMatrix, 4, 1)

print("+------------------------------------------------------------------------+")
printAdjacencyMatrix(adjacentMatrix)
print("+------------------------------------------------------------------------+")

Output :


   +------------------------------------------------------------------------+
   |     0      | |     1      | |     1      | |     1      | |     0      | 
   |     1      | |     0      | |     0      | |     0      | |     1      | 
   |     1      | |     0      | |     0      | |     1      | |     1      | 
   |     1      | |     0      | |     1      | |     0      | |     1      | 
   |     0      | |     1      | |     1      | |     1      | |     0      | 
   +------------------------------------------------------------------------+

Code explanation for Adjacency Matrix Data Structure

The code for Adjacency Matrix is quite simple.

There are two important methods defined above :

def insertEdge(adjacentMatrix, i, j)

def removeEdge(adjacentMatrix, i, j)

As the name of the method suggests insertEdge(...), is used to add an Edge to the Adjacency Matrix.

Explanation of 'def insertEdge(adjacentMatrix, i, j)' method :

def insertEdge(adjacentMatrix, i, j):
	adjacentMatrix[i][j] = True

So, the actual adjacency matrix, we are going to create, looks like the below structure,

Now, if we look at the min program. We create a 2D array, that holds either True or False.

V = 5
adjacentMatrix = [[False for i in range(V)] for j in range(V)]

So, the above line creates a 2D array with 5 rows and 5 columns that initially contains False.

Now, all we need to do is, wherever we want to insert an edge. We will mark it with value True.

Say, for example :

There is an edge in [0][1] (As mentioned in the adjacency matrix above).

All we are doing is, calling the def insertEdge(...) method,

insertEdge(adjacentMatrix, 0, 1)

and passing 0 and 1 as parameters.

And in the def insertEdge(...) method, we have the below line,

adjacentMatrix[i][j] = True

Now, since value of i = 0 and j = 1,

adjacentMatrix[0][1] = True;

And adjacentMatrix[0][1] is marked to true.

In other words, we have inserted an edge in adjacentMatrix[0][1] above.

Similarly, we insert the edges one by one, calling the void insertEdge(...) method.

insertEdge(adjacentMatrix, 0, 2)
insertEdge(adjacentMatrix, 0, 3)
...
...
...

Explanation of 'def removeEdge(adjacentMatrix, i, j)' method :

Even, to delete an Edge, we follow the same steps.

As we know, there is an Edge in [0][2]. To remove it, all we need to do is call,

removeEdge(adjacentMatrix, 0, 2);

And mark that particular location to false.

def removeEdge(adjacentMatrix, i, j):
	adjacentMatrix[i][j] = False

And the Edge is deleted.

❮❮ PREV NEXT ❯❯