SCC
|
Document last modified:
|
DFS(G) is given below.
- Complete the table for G.
| G |
a |
b |
c |
d |
e |
f |
g |
h |
| d |
1 |
2 |
3 |
5 |
8 |
9 |
13 |
14 |
| f |
12 |
7 |
4 |
6 |
11 |
10 |
16 |
15 |
| π |
NIL |
a |
b |
c |
a |
e |
NIL |
g |
- Give f[u] in decreasing order. g,h,a,e,f,b,d,c
- Draw GT.
- Find DFS(GT), in the main loop of DFS
consider the vertices in order of decreasing f[u]. Assume that the adjacency list is ordered alphabetically. Show the discovery
and finishing times for each vertex (d on the left and f on the right side
of the node).
| GT |
a |
b |
c |
d |
e |
f |
g |
h |
| d |
5 |
7 |
6 |
9 |
10 |
12 |
1 |
3 |
| f |
16 |
8 |
15 |
14 |
11 |
13 |
2 |
4 |
| π |
NIL |
c |
a |
c |
d |
e |
NIL |
NIL |
- On the graph above, circle GSCC
GSCC
