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.

**Solution**

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

Floyd-Warshall

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];

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 */

else

return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);

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 */

else

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