Kosaraju's algorithm
id:
kosaraju-s-algorithm-292-6524796
title:
Kosaraju's algorithm
text:
In computer science, Kosaraju-Sharir's algorithm is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph has exactly the same strongly connected components as the original graph.
brand slug:
wiki
category slug:
encyclopedia
description:
Method of finding a directed graph's strongly connected components
original url:
https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
date created:
date modified:
2023-11-12T00:12:48Z
main entity:
{"identifier":"Q2655281","url":"https://www.wikidata.org/entity/Q2655281"}
image:
fields total:
13
integrity:
14