The Kosaraju–Sharir's algorithm is used to identify strongly connected components (SCCs) in directed graphs. It runs in O(V + E) time, since it performs two depth-first searches (DFS) and uses the transposed graph.
Consider the directed graph with vertices {0, 1, 2, 3, 4, 5, 6, 7} and edges:
(0 → 1), (1 → 2), (2 → 0), (2 → 3), (3 → 4), (4 → 5), (4 → 7), (4 → 6), (5 → 6), (6 → 7)
Regarding the application of the Kosaraju–Sharir's algorithm to this graph, select the correct alternative:
a) The algorithm finds four strongly connected components: {0,1,2}, {3}, {4,5,6} and {7}.
b) The algorithm finds three strongly connected components: {0,1,2}, {3} and {4,5,6,7}.
c) The algorithm cannot be applied to directed graphs, only to undirected graphs.
d) The algorithm finds eight strongly connected components, each vertex being isolated.
e) None of the above.
Original idea by: Pedro Pereira
Questão interessante. A resposta me parece ser (E), correto? As componentes são 012, e os demais cada um por si.
ResponderExcluirOk, mudamos as setas e a ordem das alternativas, e ficamos com a questão.
Excluir