Path-based strong component algorithm - Revision history

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:36Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 85:		Line 85:
	\| year = 2004}}.		\| year = 2004}}.

	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Graph connectivity]]		[[Category:Graph connectivity]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:48Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 85:		Line 85:
	\| year = 2004}}.		\| year = 2004}}.

	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Graph connectivity]]		[[Category:Graph connectivity]]

IznoRepeat: /* References */cleaning :Category:CS1 maint: multiple names: authors list (Jr), genfixes

2024-03-27T22:07:31Z

References: cleaning Category:CS1 maint: multiple names: authors list (Jr), genfixes

← Previous revision		Revision as of 22:07, 27 March 2024
Line 66:		Line 66:
	\| doi=10.1016/0020-0190(71)90006-8}}.		\| doi=10.1016/0020-0190(71)90006-8}}.
	*{{citation		*{{citation
	\| last = Purdom \| first = P., Jr.		\| last = Purdom \| first = P. Jr.
	\| journal = BIT		\| journal = BIT
	\| pages = 76–94		\| pages = 76–94

Tc14Hd at 10:56, 14 March 2024

2024-03-14T10:56:57Z

← Previous revision		Revision as of 10:56, 14 March 2024
Line 1:		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>		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>

Mathnerd314159: /* References */ url for convenience

2022-10-22T00:11:26Z

References: url for convenience

← Previous revision		Revision as of 00:11, 22 October 2022
Line 53:		Line 53:
	\| title = Path-based depth-first search for strong and biconnected components		\| title = Path-based depth-first search for strong and biconnected components
	\| volume = 74		\| volume = 74
	\| year = 2000~~}}.~~		\| year = 2000
			\| url = https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/path%20based...pdf}}.
	*{{citation		*{{citation
	\| last = Munro \| first = Ian \| author-link = Ian Munro (computer scientist)		\| last = Munro \| first = Ian \| author-link = Ian Munro (computer scientist)

David Eppstein: /* References */ also Ian Munro (computer scientist)

2021-07-06T05:40:30Z

References: also Ian Munro (computer scientist)

← Previous revision		Revision as of 05:40, 6 July 2021
Line 55:		Line 55:
	\| year = 2000}}.		\| year = 2000}}.
	*{{citation		*{{citation
	\| last = Munro \| first = Ian		\| last = Munro \| first = Ian \| author-link = Ian Munro (computer scientist)
	\| journal = Information Processing Letters		\| journal = Information Processing Letters
	\| pages = 56–58		\| pages = 56–58

David Eppstein: /* References */ Harold N. Gabow

2021-07-06T05:39:59Z

References: Harold N. Gabow

← Previous revision		Revision as of 05:39, 6 July 2021
Line 45:		Line 45:
	\| year = 1976}}.		\| year = 1976}}.
	*{{citation		*{{citation
	\| last = Gabow \| first = Harold N.		\| last = Gabow \| first = Harold N. \| author-link = Harold N. Gabow
	\| doi = 10.1016/S0020-0190(00)00051-X		\| doi = 10.1016/S0020-0190(00)00051-X
	\| issue = 3–4		\| issue = 3–4

84.245.120.190: /* Description */ add edge types

2020-11-30T23:03:26Z

Description: add edge types

← Previous revision		Revision as of 23:03, 30 November 2020
Line 10:		Line 10:
	#Push ''v'' onto ''S'' and also onto ''P''.		#Push ''v'' onto ''S'' and also onto ''P''.
	#For each edge from ''v'' to a neighboring vertex ''w'':		#For each edge from ''v'' to a neighboring vertex ''w'':
	#* If the preorder number of ''w'' has not yet been assigned, recursively search ''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:		#*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''.		#**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'':		#If ''v'' is the top element of ''P'':

Citation bot: Alter: issue. Add: url, s2cid, issue. Formatted dashes. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform

2020-09-06T01:09:14Z

Alter: issue. Add: url, s2cid, issue. Formatted dashes. | You can use this bot yourself. Report bugs here. | Suggested by SemperIocundus | via #UCB_webform

← Previous revision		Revision as of 01:09, 6 September 2020
Line 34:		Line 34:
	\| title = Algorithms for dense graphs and networks on the random access computer		\| title = Algorithms for dense graphs and networks on the random access computer
	\| volume = 15		\| volume = 15
	\| year = 1996~~}}.~~		\| year = 1996\| issue = 6
			\| s2cid = 8930091
			}}.
	*{{citation		*{{citation
	\| last = Dijkstra \| first = Edsger \| author-link = Edsger Dijkstra		\| last = Dijkstra \| first = Edsger \| author-link = Edsger Dijkstra
Line 45:		Line 47:
	\| last = Gabow \| first = Harold N.		\| last = Gabow \| first = Harold N.
	\| doi = 10.1016/S0020-0190(00)00051-X		\| doi = 10.1016/S0020-0190(00)00051-X
	\| issue = ~~3-4~~		\| issue = 3–4
	\| journal = Information Processing Letters		\| journal = Information Processing Letters
	\| mr = 1761551		\| mr = 1761551
Line 59:		Line 61:
	\| volume = 1		\| volume = 1
	\| year = 1971		\| year = 1971
			\| issue = 2
	\| doi=10.1016/0020-0190(71)90006-8}}.		\| doi=10.1016/0020-0190(71)90006-8}}.
	*{{citation		*{{citation
Line 67:		Line 70:
	\| volume = 10		\| volume = 10
	\| year = 1970		\| year = 1970
	\| doi=10.1007/bf01940892~~}}.~~		\| doi=10.1007/bf01940892\| s2cid = 20818200
			\| url = http://digital.library.wisc.edu/1793/57514
			}}.
	*{{citation		*{{citation
	\| last = Sedgewick \| first = R.		\| last = Sedgewick \| first = R.

64.46.18.204: /* Description */

2019-03-09T19:06:32Z

Description

← Previous revision		Revision as of 19:06, 9 March 2019
Line 11:		Line 11:
	#For each edge from ''v'' to a neighboring vertex ''w'':		#For each edge from ''v'' to a neighboring vertex ''w'':
	#* If the preorder number of ''w'' has not yet been assigned, recursively search ''w'';		#* If the preorder number of ''w'' has not yet been assigned, recursively search ''w'';
	#*Otherwise, if ''w'' has ~~already~~ been assigned to a strongly connected component:		#*Otherwise, if ''w'' has not yet been assigned to a strongly connected component:
	#**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''.		#**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'':		#If ''v'' is the top element of ''P'':