Path-based strong component algorithm: Difference between revisions

Revision as of 20:54, 5 December 2010

Latest revision as of 19:57, 12 October 2024

(21 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Graph algorithm}}

In [[graph theory]], the '''Cheriyan–Mehlhorn/Gabow algorithm''' is a [[linear-time]] method for finding the [[strongly connected component]]s of a [[directed graph]].<ref>{{citation

In [[graph theory]], the [[strongly connected component]]s of a [[directed graph]] may be found using an algorithm that uses [[depth-first search]] in combination with two [[stack (data structure)|stacks]], one to keep track of the vertices in the current component and the second to keep track of the current search path.<ref>{{harvtxt|Sedgewick|2004}}.</ref> Versions of this algorithm have been proposed by {{harvtxt|Purdom|1970}}, {{harvtxt|Munro|1971}}, {{harvtxt|Dijkstra|1976}}, {{harvtxt|Cheriyan|Mehlhorn|1996}}, and {{harvtxt|Gabow|2000}}; of these, Dijkstra's version was the first to achieve [[linear time]].<ref>[http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html History of Path-based DFS for Strong Components], Harold N. Gabow, accessed 2012-04-24.</ref>

| last = Sedgewick | first = R.

| contribution = 19.8 Strong Components in Digraphs

| edition = 3rd

| ___location = Cambridge MA

| pages = 205–216

| publisher = Addison-Wesley

| title = Algorithms in Java, Part 5 – Graph Algorithms

| year = 2004}}</ref> It was discovered in 1996 by Joseph Cheriyan and [[Kurt Mehlhorn]]<ref>{{citation

| last1 = Cheriyan | first1 = J.

| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn

| doi = 10.1007/BF01940880

| journal = [[Algorithmica]]

| pages = 521–549

| title = Algorithms for dense graphs and networks on the random access computer

| volume = 15

| year = 1996}}</ref>

and rediscovered in 1999 by [[Harold N. Gabow]].<ref>{{citation

| last = Gabow | first = H.N.

| contribution = Searching (Ch 10.1)

| editor1-last = Gross | editor1-first = J. L.

| editor2-last = Yellen | editor2-first = J.

| pages = 953–984

| publisher = CRC Press

| title = Discrete Math. and its Applications: Handbook of Graph Theory

| volume = 25

| year = 2003}}</ref>

Like [[Tarjan's strongly connected components algorithm]], it performs a single [[depth first search]] of the given graph, using a [[Stack (data structure)|stack]] to keep track of vertices that have not yet been assigned to a component, and moving these vertices into a new component when it finishes expanding the final vertex of its component. However, unlike Tarjan's algorithm, which uses a vertex-indexed [[array data structure|array]] of [[Depth-first search|preorder numbers]] to keep track of when to form a new component, Gabow's algorithm uses a second stack for this purpose.

==Description==

The algorithm performs a depth-first search of the given graph ''G'', maintaining as it does two stacks ''S'' and ''P'' (in addition to the normal call stack for a recursive function).

Stack ''S'' contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices.

Stack ''P'' contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter ''C'' of the number of vertices reached so far, which it uses to compute the [[preorder]] numbers of the vertices.

When the depth-first search reaches a vertex ''v'', the algorithm performs the following steps:

Line 38 ⟶ 11:

#Push ''v'' onto ''S'' and also onto ''P''.

#For each edge from ''v'' to a neighboring vertex ''w'':

#* If the preorder number of ''w'' has not yet been assigned (the edge is a [[Depth-first search#Output of a depth-first search|tree edge]]), recursively search ''w'';

#*Otherwise, if ''w'' has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):

#**Repeatedly pop vertices from ''P'' until the top element of ''P'' has a preorder number less than or equal to the preorder number of ''w''.

#If ''v'' is the top element of ''P'':

Line 46 ⟶ 19:

The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.

== References ==

==Related algorithms==

Like this algorithm, [[Tarjan's strongly connected components algorithm]], italso performsuses a single [[depth first search]] oftogether the given graph, usingwith a [[Stack (data structure)|stack]] to keep track of vertices that have not yet been assigned to a component, and movingmoves these vertices into a new component when it finishes expanding the final vertex of its component. However, unlikein place of the stack ''P'', Tarjan's algorithm, which uses a vertex-indexed [[array (data structuretype)|array]] of preorder numbers, assigned in the order that vertices are first visited in the [[Depthdepth-first search|preorder numbers]]. The preorder array is used to keep track of when to form a new component, Gabow's algorithm uses a second stack for this purpose.

==Notes==

{{reflist}}

== References ==

*{{citation

| last1 = Cheriyan | first1 = J.

| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn

| doi = 10.1007/BF01940880

| journal = [[Algorithmica]]

| pages = 521–549

| title = Algorithms for dense graphs and networks on the random access computer

| volume = 15

| year = 1996}}</ref>| issue = 6

| s2cid = 8930091

}}.

*{{citation

| last = Dijkstra | first = Edsger | author-link = Edsger Dijkstra

| ___location = NJ

| at = Ch.&nbsp;25

| publisher = CRCPrentice PressHall

| title = A Discipline of Programming

| year = 20031976}}</ref>.

*{{citation

| last = Gabow | first = Harold N. | author-link = Harold N. Gabow

| doi = 10.1016/S0020-0190(00)00051-X

| issue = 3–4

| journal = Information Processing Letters

| mr = 1761551

| pages = 953–984107–114

| title = Path-based depth-first search for strong and biconnected components

| volume = 2574

| year = 2000

| url = https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/path%20based...pdf}}.

*{{citation

| last = Munro | first = Ian | author-link = Ian Munro (computer scientist)

| journal = Information Processing Letters

| pages = 56–58

| title = Efficient determination of the transitive closure of a directed graph

| volume = 1

| year = 1971

| issue = 2

| doi=10.1016/0020-0190(71)90006-8}}.

*{{citation

| last = GabowPurdom | first = HP.N Jr.

| journal = BIT

| pages = 76–94

| title = A transitive closure algorithm

| volume = 10

| year = 1970

| doi=10.1007/bf01940892| s2cid = 20818200

| url = http://digital.library.wisc.edu/1793/57514

}}.

*{{citation

| last = Sedgewick | first = R.

| contribution = 19.8 Strong Components in Digraphs

| edition = 3rd

| ___location = Cambridge MA

| pages = 205–216

| publisher = Addison-Wesley

| title = Algorithms in Java, Part 5 – Graph Algorithms

| year = 2004}}.

[[Category:Graph algorithms]]