Adjacency Matrix in Python
Given the edges of a graph as a list of tuples, construct an adjacency matrix to represent the graph in Python.
Examples:
Input:
V = 3
(Number of vertices)edges = [(0, 1), (1, 2), (2, 0)]
Output:
[ [0, 1, 1],
[1, 0, 1],
[1, 1, 0]]
Input:
V = 4
(Number of vertices)edges = [(0, 1), (1, 2), (1, 3), (2, 3), (3, 0)]
Output:
[ [0, 1, 0, 1],
[1, 0, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 0]]
step-by-step algorithm:
- Initialize an empty V×V matrix with all zeros.
- For each edge (u,v) in the given list of edges, set
matrix[u][v] = 1
andmatrix[v][u] = 1
(since the graph is undirected).
Below is the implementation of the algorithm:
def create_adjacency_matrix(V, edges):
# Initialize an empty V x V matrix with all zeros
matrix = [[0] * V for _ in range(V)]
# Populate the matrix based on the edges
for edge in edges:
u, v = edge
matrix[u][v] = 1
matrix[v][u] = 1 # Undirected graph
return matrix
# Example 1
V1 = 3
edges1 = [(0, 1), (1, 2), (2, 0)]
adj_matrix1 = create_adjacency_matrix(V1, edges1)
for row in adj_matrix1:
print(row)
print()
# Example 2
V2 = 4
edges2 = [(0, 1), (1, 2), (1, 3), (2, 3), (3, 0)]
adj_matrix2 = create_adjacency_matrix(V2, edges2)
for row in adj_matrix2:
print(row)
Output
[0, 1, 1] [1, 0, 1] [1, 1, 0] [0, 1, 0, 1] [1, 0, 1, 1] [0, 1, 0, 1] [1, 1, 1, 0]
Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V^2)
Contact Us