Consider the following directed graph for each of the problems: Note: The algori
ID: 3567991 • Letter: C
Question
Consider the following directed graph for each of the problems:
Note:
The algorithm for finding strongly connected components of a graph G = (V, E) uses the transpose of G, which is defined to be the graph GT= (V, ET), where ET = {(u, v) : (v, u) ? E}. That is, ETconsists of the edges of G with their directions reversed. Given an adjacency-list representation ofG, the time to create GT is O(V + E). It is interesting to observe that G and GT have exactly the same strongly connected components: u and v are reachable from each other in G if and only if they are reachable from each other in GT.
Explanation / Answer
4 Strongly Connected Components:
(A, B, H)
(D, G, F)
(I, J, K, C)
(E)