Kosaraju Algorithm in C, Java and Python

[Kumar-laxmi]

Feature = Kosaraju Algorithm

Kosaraju's algorithm is a graph algorithm used to find strongly connected components (SCCs) in a directed graph. A strongly connected component is a subset of vertices in a graph where there is a path between any two vertices within the subset. The algorithm addresses the problem of identifying these strongly connected components.

• Kosaraju's algorithm is based on the concept of reversing edges and utilizing two DFS passes.
• The first pass is used to obtain the finish times of vertices in the original graph.
• The second pass performs DFS on the transposed graph using the order of finish times obtained in the first pass

Approach :

Kosaraju's algorithm utilizes depth-first search (DFS) and a two-pass approach to find strongly connected components in a directed graph. It performs the following steps:

1 First Pass (DFS):

• Perform a depth-first search (DFS) on the original graph, exploring vertices in any order.
• During the DFS traversal, record the order in which vertices finish their recursive DFS calls (i.e., finish times) in a stack or list.

2. Graph Transposition:

   • Transpose the original graph by reversing the direction of all edges.
   • This creates a new graph with the same vertices but with reversed edges.

3. Second Pass (DFS on Transposed Graph):

Additional context

[tarunvyshnav777]

@Kumar-laxmi kindly assign this to me under SSOC'23

[Devchawla2608]

@Kumar-laxmi please assign this to me under SSOC'23. I'm ready to contribute in all 4 languages

[shanvijha30]

@Kumar-laxmi I would like to work on this issue could you please assign it to me. Thank you!

[Mrudula1205]

@Kumar-laxmi I would like to work on this issue. Please assign it to me under SSoC'23

[Ashutoshbind15]

@Kumar-laxmi I would like to work on this under ssoc'23, Have also implemented it quite a few times. Haven't yet contributed to the algorithms repository this season.

[Kumar-laxmi]

Assigned! @shanvijha30 : C, Java & Python

[github-actions[bot]]

Stale issue message