Question

JAVA

Describe an efficient algorithm that converts the Adjacency list representation of a graph to the Adjacency matrix representation of the same graph. What is the running time?

1. Use pseudocode.

2. What is the running time?

Example:

Input: The adjacency list is:
Adj[0] -> 2
Adj[1] -> 2
Adj[2] -> 0 -> 1

Output: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]

Answer 1

/*If you any query do comment in the comment section else like the solution*/

function adjacencyMatrix(mat[V][V]) {
    queue q
    q.add(srcNode)
    visited.add(srcNode)
    while q is not empty 
        front = q.front()
        while(Adj[front] != adj[front].end)
            if adj[front] is not visited
                mat[front][adj[front]] = 1
                visited.add(adj[front])
        q.pop()
    return mat
}

Time Complexity: We are doing bfs in which each node is visited only once so the time complexity will be O(V+E) where V is number of vertices and E is the number of edges.