Quiz question 5 (05/05/2023) - Strongly Connected Components
Considering the following directed graph:
I. Since this is a strongly connected graph, it does not have a topological sort.
II. We can easily find the topological sort from this graph using the reverse order of finishing time from DFS.
III. By applying Kosaraju-Sharir’s algorithm to this graph, we can obtain a set of strongly connected components in the order [{C}, {D, E, F}, {A}, {B}].
IV. Kosaraju-Sharir’s algorithm can find the topological sort of any directed graph even if it has cycles, in this case treating each strongly connected component as a single node. In this particular graph, the last node in the topological sort could be either A or B.
What statements from the options above are correct?- I and III
- II and IV
- III and IV
- III
- none of above
Good question. I'll take it.
ReplyDelete