Path-based strong component algorithm: Difference between revisions

Revision as of 19:06, 9 March 2019

Latest revision as of 19:57, 12 October 2024

(8 intermediate revisions by 7 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>

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