Content deleted Content added
m format |
m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 |
||
| (40 intermediate revisions by 25 users not shown) | |||
Line 1:
{{Short description|Graph algorithm}}
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>
==
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:
#Set the preorder number of ''v'' to ''C'', and increment ''C''.
#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'':
#*Pop vertices from ''S'' until ''v'' has been popped, and assign the popped vertices to a new component.
#*Pop ''v'' from ''P''.
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.
==Related algorithms==
[[Category:Algorithms]]▼
Like this algorithm, [[Tarjan's strongly connected components algorithm]] also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack ''P'', Tarjan's algorithm uses a vertex-indexed [[array (data type)|array]] of preorder numbers, assigned in the order that vertices are first visited in the [[depth-first search]]. The preorder array is used to keep track of when to form a new component.
[[Category:Graph theory]]▼
==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| issue = 6
| s2cid = 8930091
}}.
*{{citation
| last = Dijkstra | first = Edsger | author-link = Edsger Dijkstra
| ___location = NJ
| at = Ch. 25
| publisher = Prentice Hall
| title = A Discipline of Programming
| year = 1976}}.
*{{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 = 107–114
| title = Path-based depth-first search for strong and biconnected components
| volume = 74
| 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 = Purdom | first = P. 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}}.
| |||