25:
149:
direction), and to enumerate the in-neighbours of a vertex (traverse edges in the backward direction); however the last can be done without, at the price of constructing a representation of the transpose graph during the forward traversal phase. The only additional data structure needed by the algorithm is an ordered list
148:
The primitive graph operations that the algorithm uses are to enumerate the vertices of the graph, to store data per vertex (if not in the graph data structure itself, then in some table that can use vertices as indices), to enumerate the out-neighbours of a vertex (traverse edges in the forward
298:
Trivial variations are to instead assign a component number to each vertex, or to construct per-component lists of the vertices that belong to it. The unvisited/visited indication may share storage location with the final assignment of root for a vertex.
765:
517:
following outward edges at each step of path). Hence all these form a single strongly connected component. Moreover, no vertex remains, because, to be in this strongly connected component a vertex must be reachable from
156:
If strong components are to be represented by appointing a separate root vertex for each component, and assigning to each vertex the root vertex of its component, then
Kosaraju's algorithm can be stated as follows.
833:
864:
because there is a matching lower bound (any algorithm must examine all vertices and edges). It is the conceptually simplest efficient algorithm, but is not as efficient in practice as
865:
54:
136:. 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
642:
869:
140:(the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
936:
76:
549:
hasn't been assigned to any component, we can be sure that all the vertices to the left have made their connected components; that
302:
The key point of the algorithm is that during the first (forward) traversal of the graph edges, vertices are prepended to the list
314:
was first visited because it appeared in the enumeration of all vertices or because it was the out-neighbour of another vertex
381:
has an inward link from any of the blocks beginning at some vertex to its right, i.e., the blocks corresponding to vertices
109:
37:
979:
779:
47:
41:
33:
377:
using just outward edges at each node in the path. It is important to note that no vertex in the block beginning at
927:
860:, Kosaraju's algorithm performs two complete traversals of the graph and so runs in Θ(V+E) (linear) time, which is
974:
58:
959:
406:
in the list. This is so, because otherwise the vertex having the inward link(say from the block beginning at
861:
914:
569:
557:
doesn't point to any of the vertices to the left of it. Also, since, no edge from higher blocks to
565:
932:
900:
530:, if any, lie in the first block only, and all the vertices in first block are reachable from
125:
918:
910:
896:
876:
121:
90:
310:
relative to the search tree being explored. This means it does not matter whether a vertex
137:
129:
922:
857:
771:
770:
Set intersection is computationally costly, but it is logically equivalent to a double
307:
113:
968:
892:
117:
760:{\displaystyle B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).}
942:
133:
430:, which is a contradiction. On the other hand, vertices in the block starting at
575:
The algorithm can be understood as identifying the strong component of a vertex
358:
both belong to the same strong component, in which case their relative order in
102:
945:. A strong-connectivity algorithm and its applications to data flow analysis.
105:
534:. So the algorithm chooses all the vertices in the connected component of
632:
after phase 2 of the algorithm, the strong component containing a vertex
478:
as higher blocks can't have links pointing to vertices in the block of
837:
it becomes sufficient to test whether a newly encountered element of
373:, where the block consists of all the vertices reachable from vertex
474:. Note that these vertices can only lie in the block beginning at
16:
Method of finding a directed graph's strongly connected components
470:, assigns all vertices which point to it, the same component as
153:
of graph vertices, that will grow to contain each vertex once.
494:
are added too, and so on till no more vertices can be added.
18:
490:. Subsequently, all the vertices pointing to these vertices,
960:
Good Math, Bad Math: Computing
Strongly Connected Components
501:, from all the vertices added to the component containing
437:
edges pointing to the blocks starting at some vertex in
782:
645:
624:
for the set of vertices which appear strictly before
564:
As given above, the algorithm for simplicity employs
505:. And there is a path to all the vertices added from
422:)would have been already visited and pre-pended to
284:
251:
247:
214:
185:
181:
827:
759:
583:both by backwards and forwards traversal. Writing
872:, which perform only one traversal of the graph.
848:has already been assigned to a component or not.
572:as long as the post-order property is preserved.
369:of the list can be made to correspond to a block
866:Tarjan's strongly connected components algorithm
828:{\displaystyle B(u)\setminus F(u)\subseteq P(u)}
579:as the set of vertices which are reachable from
553:doesn't belong to any of those components; that
513:(which contains all the vertices reachable from
46:but its sources remain unclear because it lacks
509:, as all those lie in the block beginning at
8:
482:. Let the set of all vertices that point to
268:as belonging to the component whose root is
947:Computers and Mathematics with Applications
261:has not been assigned to a component then:
561:'s block exists, the proof remains same.
856:Provided the graph is described using an
781:
644:
77:Learn how and when to remove this message
795:
739:
706:
688:
609:for the set of vertices reachable from
594:for the set of vertices reachable from
330:is, so if there is a forward path from
526:. All vertices that are able to reach
870:path-based strong component algorithm
466:Step 3 of the algorithm, starts from
7:
931:, 3rd edition. The MIT Press, 2009.
875:If the graph is represented as an
14:
568:, but it could just as well use
23:
905:Data Structures and Algorithms
822:
816:
807:
801:
792:
786:
751:
745:
736:
730:
721:
718:
712:
703:
697:
691:
685:
679:
670:
664:
655:
649:
365:This means, that each element
1:
545:, in the loop of step 3, and
318:that got visited; either way
254:is the recursive subroutine:
188:is the recursive subroutine:
110:strongly connected components
613:by backwards traversal, and
95:Kosaraju-Sharir's algorithm
996:
928:Introduction to Algorithms
522:and must be able to reach
879:, the algorithm requires
32:This article includes a
907:. Addison-Wesley, 1983.
205:For each out-neighbour
61:more precise citations.
862:asymptotically optimal
829:
761:
598:by forward traversal,
275:For each in-neighbour
830:
762:
636:appointed as root is
541:When we reach vertex
322:will be prepended to
292:Otherwise do nothing.
233:Otherwise do nothing.
915:Charles E. Leiserson
780:
643:
570:breadth-first search
99:Kosaraju's algorithm
497:There is a path to
342:will appear before
195:is unvisited then:
165:of the graph, mark
980:Graph connectivity
825:
757:
566:depth-first search
346:on the final list
169:as unvisited. Let
34:list of references
949:7(1):67–72, 1981.
901:Jeffrey D. Ullman
238:For each element
87:
86:
79:
987:
975:Graph algorithms
919:Ronald L. Rivest
911:Thomas H. Cormen
897:John E. Hopcroft
877:adjacency matrix
847:
836:
834:
832:
831:
826:
766:
764:
763:
758:
635:
631:
627:
623:
612:
608:
597:
593:
582:
578:
560:
556:
552:
548:
544:
537:
533:
529:
525:
521:
516:
512:
508:
504:
500:
493:
489:
485:
481:
477:
473:
469:
463:
433:
429:
426:in the block of
425:
421:
405:
380:
376:
372:
368:
362:is arbitrary).
361:
357:
353:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
305:
286:
282:
278:
271:
267:
260:
253:
249:
245:
241:
227:
223:
216:
212:
208:
201:
194:
187:
183:
180:of the graph do
179:
176:For each vertex
172:
168:
164:
161:For each vertex
152:
91:computer science
82:
75:
71:
68:
62:
57:this article by
48:inline citations
27:
26:
19:
995:
994:
990:
989:
988:
986:
985:
984:
965:
964:
956:
889:
854:
838:
778:
777:
775:
641:
640:
633:
629:
625:
614:
610:
599:
595:
584:
580:
576:
558:
554:
550:
546:
542:
535:
531:
527:
523:
519:
514:
510:
506:
502:
498:
491:
487:
483:
479:
475:
471:
467:
457:
447:
438:
431:
427:
423:
420:
407:
400:
390:
382:
378:
374:
370:
366:
359:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
311:
303:
280:
276:
269:
265:
258:
243:
239:
225:
221:
210:
206:
199:
192:
177:
170:
166:
162:
150:
146:
138:transpose graph
130:S. Rao Kosaraju
97:(also known as
83:
72:
66:
63:
52:
38:related reading
28:
24:
17:
12:
11:
5:
993:
991:
983:
982:
977:
967:
966:
963:
962:
955:
954:External links
952:
951:
950:
940:
923:Clifford Stein
908:
888:
885:
858:adjacency list
853:
850:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
772:set difference
768:
767:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
452:
443:
415:
395:
386:
296:
295:
294:
293:
290:
289:
288:
285:Assign(v,root)
273:
252:Assign(u,root)
236:
235:
234:
231:
230:
229:
218:
203:
174:
145:
142:
114:directed graph
85:
84:
42:external links
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
992:
981:
978:
976:
973:
972:
970:
961:
958:
957:
953:
948:
944:
941:
938:
937:0-262-03384-4
934:
930:
929:
924:
920:
916:
912:
909:
906:
902:
898:
894:
893:Alfred V. Aho
891:
890:
886:
884:
882:
878:
873:
871:
867:
863:
859:
851:
849:
845:
841:
819:
813:
810:
804:
798:
789:
783:
773:
754:
748:
742:
733:
727:
724:
715:
709:
700:
694:
682:
676:
673:
667:
661:
658:
652:
646:
639:
638:
637:
621:
617:
606:
602:
591:
587:
573:
571:
567:
562:
539:
495:
464:
461:
455:
451:
446:
442:
436:
418:
414:
410:
404:
398:
394:
389:
385:
363:
309:
300:
291:
274:
263:
262:
256:
255:
246:in order, do
237:
232:
219:
204:
197:
196:
190:
189:
175:
160:
159:
158:
154:
144:The algorithm
143:
141:
139:
135:
131:
128:credit it to
127:
123:
119:
115:
111:
107:
104:
100:
96:
92:
81:
78:
70:
60:
56:
50:
49:
43:
39:
35:
30:
21:
20:
946:
943:Micha Sharir
926:
904:
880:
874:
855:
843:
839:
774:, and since
769:
628:on the list
619:
615:
604:
600:
589:
585:
574:
563:
540:
496:
465:
459:
453:
449:
444:
440:
434:
416:
412:
408:
402:
396:
392:
387:
383:
364:
301:
297:
155:
147:
134:Micha Sharir
108:to find the
98:
94:
88:
73:
64:
53:Please help
45:
248:Assign(u,u)
202:as visited.
103:linear time
59:introducing
969:Categories
887:References
852:Complexity
308:post-order
811:⊆
796:∖
740:∖
707:∖
689:∖
659:∩
492:In(In(L))
173:be empty.
106:algorithm
67:July 2020
868:and the
435:can have
350:(unless
220:Prepend
215:Visit(v)
186:Visit(u)
184:, where
182:Visit(u)
122:Hopcroft
835:
776:
326:before
264:Assign
101:) is a
55:improve
935:
883:time.
250:where
126:Ullman
543:v = L
488:In(L)
338:then
283:, do
213:, do
198:Mark
112:of a
40:, or
933:ISBN
881:Ο(V)
458:, …
401:, …
354:and
270:root
132:and
124:and
538:.
486:be
409:n'
334:to
306:in
279:of
257:If
242:of
224:to
209:of
191:If
118:Aho
116:.
89:In
971::
925:.
921:,
917:,
913:,
903:.
899:,
895:,
462:}.
456:+1
448:,
428:n'
419:+1
411:≥
399:+1
391:,
120:,
93:,
44:,
36:,
939:.
846:)
844:u
842:(
840:B
823:)
820:u
817:(
814:P
808:)
805:u
802:(
799:F
793:)
790:u
787:(
784:B
755:.
752:)
749:u
746:(
743:P
737:)
734:u
731:(
728:B
725:=
722:)
719:)
716:u
713:(
710:F
704:)
701:u
698:(
695:B
692:(
686:)
683:u
680:(
677:B
674:=
671:)
668:u
665:(
662:F
656:)
653:u
650:(
647:B
634:u
630:L
626:u
622:)
620:u
618:(
616:P
611:u
607:)
605:u
603:(
601:B
596:u
592:)
590:u
588:(
586:F
581:u
577:u
559:v
555:v
551:v
547:v
536:L
532:L
528:L
524:L
520:L
515:L
511:L
507:L
503:L
499:L
484:L
480:L
476:L
472:L
468:L
460:N
454:n
450:i
445:n
441:i
439:{
432:n
424:L
417:n
413:i
403:N
397:n
393:i
388:n
384:i
379:n
375:n
371:L
367:n
360:L
356:v
352:u
348:L
344:v
340:u
336:v
332:u
328:u
324:L
320:v
316:u
312:v
304:L
287:.
281:u
277:v
272:.
266:u
259:u
244:L
240:u
228:.
226:L
222:u
217:.
211:u
207:v
200:u
193:u
178:u
171:L
167:u
163:u
151:L
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.