Path-based strong component algorithm: Difference between revisions

Revision as of 07:57, 25 May 2014

Latest revision as of 19:57, 12 October 2024

(13 intermediate revisions by 10 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], HalHarold N. Gabow, accessed 2012-04-24.</ref>

==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.

Line 10 ⟶ 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 20 ⟶ 21:

==Related 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 second 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.

==Notes==

Line 34 ⟶ 35:

| 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

Line 43 ⟶ 46:

| year = 1976}}.

*{{citation

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

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

| issue = 3-43–4

| journal = Information Processing Letters

| mr = 1761551

Line 51 ⟶ 54:

| 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

Line 59 ⟶ 63:

| 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

Line 67 ⟶ 72:

| volume = 10

| year = 1970

| doi=10.1007/bf01940892}}.| s2cid = 20818200

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

}}.

*{{citation

| last = Sedgewick | first = R.