given a graph G, we can find its components by taking its transitive closure. After transitive closure, a nonzero entry in the matrix indicates a path of arbitrary length, not just an edge. Scanning along the first row provides a list of vertices connected to v0. The graph's components are easily extracted. Here is some code.
for(j=0;j<n;++j) { /* for each column */
for(i=0;i<n;++i) { /* for each entry in that column */
/* Or row j into row i if i→j is present */
if(!G[i][j]) continue;
for(k=0;k<n;++k) G[i][k] |= G[j][k];
}
}
For each vertex (j=1,n), this algorithm connects i→k whenever i→j and j→k. If there is a path connecting two vertices, the two end points will eventually be connected. The smallest (ordinal) vertex in the path is querried first, and its predicesor and successor are joined. Next, the neighbors of the second (ordinal) vertex in the path are joined. Eventually the endpoints must be connected.
The identity matrix trivially contains the number of walks of length 0 connecting each pair of vertices. The graph's adjacency matrix gives the number of walks of length 1, the individual edges. By induction, Gn (using matrix multiplication) contains the number of walks of length n connecting each pair of vertices. Note that this algorithm works for digraphs and graphs with multiple edges.
If you want the shortest path from vertex i to vertex j, use matrix multiplication, as described above, until a path appears, as indicated by a nonzero entry in row i column j. (This is not a terribly efficient algorithm, unless you're looking for lots of different paths in parallel.)