Note: this is an Algorithm class You are given an unweighted graph G, which is r

ID: 3780120 • Letter: N

Question

Note: this is an Algorithm class

You are given an unweighted graph G, which is represented by an adjacency matrix. Square of G is a graph G2 with the same set of vertices as G, and two vertices being adjacent if and only if the distance between them in G is 1 or 2. Example (for example, 1 and 3 are adjacent in G^2, because the distance between them in G is 2.1 and 4 are not adjacent in G2, because the distance between them in G is 3) Design an efficient algorithm to calculate an adjacency matrix of G^2. What is its running time?

Explanation / Answer

Let us assume A is the adjacency matrix for G and B is the adjacency matrix for G^2.

We will intialize all the values in B to 0. Let n be the number of vertices in A.

Algorithm:

for i in 1 to n
{
   for j in i+1 to n
   {
       B[i][j] = A[i][j]
   }
}

for i in 1 to n
{
   Create empty list L
   for j in i+1 to n
   {
       if(A[i][j]==1)
       {
           L.append(j)
       }
   }
   //We connect the nodes connected to the next node to this present node.
   for k in L (iterating over all the values in L)
   {
       for j in k+1 to n
       {
           if(A[k][j]==1)
           {
               A[i][j]=1
           }
       }
   }
}

Navigate

Note: this is a web programming class. please follow the requirment(detail) in t

Note: this is to be written in Python Rules: The game is played on a rectangular

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Note: this is an Algorithm class You are given an unweighted graph G, which is r

Question

Explanation / Answer

Related Questions

Navigate