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:

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.
5. Add the edge to the adjacency list.
6. 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.