The Kosaraju-Sharir's algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. Which of the following alternatives correctly describes the main phases of the algorithm?
A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times.
B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS.
C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs.
D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process.
E - None of the above
Original idea by: Vanessa Oliveira Alves
No comments:
Post a Comment