I am learning graph concept and got to the graph which is giving result for finding strong connected component with Kosaraju's Algorithm and Tarjan's Algorithm.
Graph: V = 4
The graph's edges are: (0, 1) (1, 2) (2, 0) (1, 3) (3, 2)
Kosaraju's Algorithm:
In Kosaraju's algorithm, I find the following SCCs:
SCC: {0, 1, 2, 3} Kosaraju's algorithm identifies one SCC that includes all four vertices.
Tarjan's Algorithm:
In Tarjan's algorithm, I find the following SCCs:
SCC: {0, 1, 2} SCC: {3} Tarjan's algorithm identifies two SCCs: one containing vertices {0, 1, 2} and the other containing vertex {3}.
Can anyone explain why we have two different result and what will be the SCC for the graph?
Whichever, directed or undirected, your graph is a single strongly connected component.
So, either there is a bug in your implementation of Tarjan, or you are trying to apply Tarjan to an directed graph, which will not work.