Question

This question is related to graph representation in Data Structure and Algorithm in Javascript.

Question 1-

Write a code in javascript in which you have to implement a function that converts

adjacency matrix to adjacency list-store and it should have following signature

function convertToAdjList( adjMatrix);

You also have to include the functions that can demonstrate your implementation work with few inputs. Submit your javascript code with output as well.

Question 2

Tell the runtime complexity of the conversion that implemented. Is it depend on the number of edges or number of vertices or both? What

should be the runtime complexity of a conversion function from

adjacency list-store to matrix be? Give the brief reasoning with some examples.

Answer 1

function convertToAdjList(adjMatrix)
{
   var adjList=[];
   for(var i=0;i<adjMatrix.length;i++)
   {
     var arr=[];
     for(var j=0;j<adjMatrix.length;j++)
     {
       if(adjMatrix[i][j]==1)
       {
        arr.push(j);
       }
     }
     adjList[i]=arr;
   }
   return adjList;
}
var A1=[[0,0,1],[0,0,1],[1,1,0]];
var A2=[[0,1,1],[1,0,0],[1,0,0]];
var A3=[[0,1,0],[1,0,1],[0,1,0]];
console.log(convertToAdjList(A1));
console.log(convertToAdjList(A1));
console.log(convertToAdjList(A1));

Here, the time complexity of this program is dependent on number of vertcies. Since, two for loops are runnning to iterate through the vertices so, its time complexity is O(V^2) where, V is number of vertices in the graph. This code goes through the whole matrix and checks if the value is 1 and when this condition becomes true, it will push the corresponding column number(j) to arr for corresponding ith vertex.For e.g in matrix A1 there is edge between 0 and 2 vertex and 1 and 2 vertex. So, For i=0 it will store 2 in array as is neighbour and for i=1 it will store 2 as its neighbour. And for i=2 as 0 and 1 both are its neighbour it will store 0,1 in arr as its neighbour. And thus, as it have to iterate through matrix of size V^2 to check whether particular pair are neighbours or not time complexity becomes V^2.

To convert adjancy list to matrix the time complexity would be O(V*E) where, E is number of edges. As we would have to go though each vertex and all of its corresponding edges.