564
Graph Algorithms
example 6
For the graph of Example 5, the initial matrix M 0 is the adjacency matrix.
M 0 = E
0 1 0 0 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 0
1 0 1 0 0
U
We know M 0 (so k = 0) and we want to compute M 1 (k + 1 = 1). Using step 1 of
Table 7.1, we consider column 1 of M 0 . Using step 2 of Table 7.1, rows 1, 2, and 4
of M 0 contain 0s in column 1, so these rows get copied directly to M 1 :
M 1 = E
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
U
Now we finish up by using step 3 of Table 7.1 Row 3 of column 1 of M 0 contains a
1, so row 3 of M 0 is or-ed with row 1 of M 0 and the result becomes the new row 3:
M 1 = E
0 1 0 0 0
0 0 1 0 0
1 1 0 1 0
0 0 0 0 0
U
Row 5 of column 1 of M 0 contains a 1, so row 5 is or-ed with row 1 and the result
becomes the new row 5:
M 1 = E
0 1 0 0 0
0 0 1 0 0
1 1 0 1 0
0 0 0 0 0
1 1 1 0 0
U
To compute the entries in M 2 , consider column 2. Rows 2 and 4 (the 0 positions in column 2) will be copied unchanged. Row 1 will be or-ed with row 2 to
give the new row 1, row 3 will be or-ed with row 2 to give the new row 3, and row
5 will be or-ed with row 2 to give the new row 5:
M 2 = E
0 1 1 0 0
0 0 1 0 0
1 1 1 1 0
0 0 0 0 0
1 1 1 0 0
U