Skip to content

Add Tarjan's algorithm #103

@ZigRazor

Description

@ZigRazor

Tarjan's algorithm for finding strongly connected components in a directed graph
Uses two main attributes of each node to track reachability, the index of that node
within a component(index), and the lowest index reachable from that node(lowlink).
We then perform a dfs of the each component making sure to update these parameters
for each node and saving the nodes we visit on the way.
If ever we find that the lowest reachable node from a current node is equal to the
index of the current node then it must be the root of a strongly connected
component and so we save it and it's equireachable vertices as a strongly
connected component.

Metadata

Metadata

Assignees

Labels

Priority:MediumPriority Label for medium priority issuecoresomething about coredevelopmentDevelopment of new FunctionalitiesenhancementNew feature or requestgood first issueGood for newcomershacktoberfesthacktoberfest issue

Projects

Status

Done

Relationships

None yet

Development

No branches or pull requests

Issue actions