Sunday, November 21, 2010

Strongly connected graph

You are given a directed graph G with n vertices labeled 1 to n.  If, for any pair of vertices I and j, I is reachable from j and vice versa, we say that G is strongly connected.  You are given a matrix T such that T[i,j] = 1 if there is an edge from vertex i to vertex j and 0, otherwise.  Using T, write programming code which returns true if G is strongly connected and false, otherwise.

//use an understanding of Floyd-warshall to solve:

procedure FloydWarshallWithPathReconstruction ()
   for k := 1 to n
       for i := 1 to n
           for j := 1 to n
               if path[i][k] + path[k][j] < path[i][j] then
                path[i][j] := path[i][k]+path[k][j];
           next[i][j] := k;

procedure GetPath (i,j)
   if path[i][j] equals infinity then
       return "no path";
   int intermediate := next[i][j];
   if intermediate equals 'null' then
       return " ";   /* there is an edge from i to j, with no vertices between */
       return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);

Thus, this produces the solution:

//given an Adjacency Matrix, A
int[,] strongly = new int[n, n];
for k=1 to n
for i=1 to n
for j= 1 to n
strongly[i,j] = (strongly[i,j] <> 9999 || (strongly[i,k] <> 9999 && strongly[k, j] <> 9999)) ? 1 : 0;

for i=1 to n
for j= 1 to n
if (strongly[i, j] != 1) return false;

return true;

No comments:

Post a Comment