Posted on by Kalkicode
Code Graph

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.

## Example

```[
[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

1. Create a graph object with the given adjacency matrix.
2. Initialize an empty adjacency list.
3. Iterate over each row and column of the matrix.
4. If a cell has a value of 1, it represents an edge between the corresponding vertices.

Here is the pseudocode for the algorithm:

```class Graph
vertices

for i = 0 to vertices
for j = 0 to vertices
if matrix[i][j] == 1

Graph(matrix)
vertices = matrix.length
for i = 0 to vertices

if u < 0 or u >= vertices or v < 0 or v >= vertices
return

printGraph()
for i = 0 to vertices
print "\n [" + i + "] :"
for j = 0 to adjacencyList.get(i).size()
if j != 0
print " → "
``` 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.

## Resultant Output Explanation

```Graph Adjacency List
 : 1 → 2 → 4
 : 0 → 2 → 4
 : 0 → 1 → 3
 : 1 → 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.

## Comment

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.

Categories
Relative Post