Construct adjacency list using adjacency matrix
In graph theory, an adjacency matrix is a square matrix used to represent a finite graph. Each cell of the matrix represents an edge between two vertices. However, the adjacency matrix can be less intuitive and inefficient when dealing with large graphs. In such cases, an adjacency list is preferred, which provides a more compact representation and faster traversal of the graph.
Problem Statement
Given an adjacency matrix, the task is to construct an adjacency list representation of the graph.
Example
Consider the following adjacency matrix:
[ [0, 1, 1, 0, 1], [1, 0, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 0, 0, 1], [1, 1, 0, 1, 0] ]
Using this matrix, we need to construct the corresponding adjacency list.
Algorithm and Pseudocode
To construct the adjacency list, we can follow these steps:
- Create a graph object with the given adjacency matrix.
- Initialize an empty adjacency list.
- Iterate over each row and column of the matrix.
- If a cell has a value of 1, it represents an edge between the corresponding vertices.
- Add the edge to the adjacency list.
- Print the adjacency list.
Here is the pseudocode for the algorithm:
class Graph vertices adjacencyList makeAdjacencyList(matrix) for i = 0 to vertices for j = 0 to vertices if matrix[i][j] == 1 addEdge(i, j) Graph(matrix) vertices = matrix.length adjacencyList = new ArrayList(matrix.length) for i = 0 to vertices adjacencyList.add(new ArrayList()) makeAdjacencyList(matrix) addEdge(u, v) if u < 0 or u >= vertices or v < 0 or v >= vertices return adjacencyList.get(u).add(v) printGraph() print "Graph Adjacency List" for i = 0 to vertices print "\n [" + i + "] :" for j = 0 to adjacencyList.get(i).size() if j != 0 print " → " print adjacencyList.get(i).get(j)

In above example adjacency matrix is form of directed graph. And adjacency list is indicates the constructed result.
Code Solution
Here given code implementation process.
-
1) Construct adjacency list by using adjacency matrix in java
2) Construct adjacency list by using adjacency matrix in c++
3) Construct adjacency list by using adjacency matrix in c#
4) Construct adjacency list by using adjacency matrix in php
5) Construct adjacency list by using adjacency matrix in node js
6) Construct adjacency list by using adjacency matrix in python
7) Construct adjacency list by using adjacency matrix in ruby
8) Construct adjacency list by using adjacency matrix in scala
9) Construct adjacency list by using adjacency matrix in swift
10) Construct adjacency list by using adjacency matrix in kotlin
11) Construct adjacency list by using adjacency matrix in vb.net
12) Construct adjacency list by using adjacency matrix in golang
Resultant Output Explanation
The resultant adjacency list for the given adjacency matrix is:
Graph Adjacency List [0] : 1 → 2 → 4 [1] : 0 → 2 → 4 [2] : 0 → 1 → 3 [3] : 1 → 4 [4] : 0 → 1 → 3
The above output shows the vertices of the graph represented as numbers in square brackets. Each vertex is followed by a colon (:) and then the list of adjacent vertices.
For example, vertex 0 is adjacent to vertices 1, 2, and 4. Similarly, vertex 1 is adjacent to vertices 0, 2, and 4.
Time Complexity
The time complexity of constructing the adjacency list using the adjacency matrix is O(V^2), where V is the number of vertices in the graph. This is because we iterate over each element in the matrix, resulting in a nested loop.
Printing the adjacency list also takes O(V^2) time, as we need to traverse the adjacency list for each vertex to display its adjacent vertices.
Finally
In this article, we discussed the problem of constructing an adjacency list from an adjacency matrix. We provided a suitable example and explained the algorithm and pseudocode for the solution. Additionally, we explained the resultant output and discussed the time complexity of the code. By using an adjacency list, we can efficiently represent and traverse graphs, making it a preferred choice for working with large graphs.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment