Strongly connected components - Revision history

Weihe at 19:07, 9 November 2014

2014-11-09T19:07:26Z

2014-11-04T15:23:01Z

← Older revision		Revision as of 15:23, 4 November 2014
Line 5:		Line 5:
	== Output ==		== Output ==

	A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness\|SCC]]. The ~~correspndence~~ between the [[Basic graph definitions#Connectedness\|SCC]] and these sets of nodes is one-to-one.		A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness\|SCC]]. The correspondence between the [[Basic graph definitions#Connectedness\|SCC]] and these sets of nodes is one-to-one.

	== Known algorithms ==		== Known algorithms ==

	# [[Kosaraju]]		# [[Kosaraju]]

2014-11-03T07:19:27Z

@@ Line 6: / Line 6: @@
 A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness|SCC]]. The correspndence between the [[Basic graph definitions#Connectedness|SCC]] and these sets of nodes is one-to-one.
 == Known algorithms ==
 # [[Kosaraju]]

2014-11-03T07:17:44Z

← Older revision		Revision as of 07:17, 3 November 2014
Line 1:		Line 1:
	~~== Definition ==~~
	~~[[File:Scc.png\|300px\|thumb\|right\|Graph with marked strongly connected components]]~~
	Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path from <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

	== Input ==		== Input ==

Line 9:		Line 5:
	== Output ==		== Output ==

	A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.		A set of sets of nodes. Each set of nodes contains exactly the nodes of one [[Basic graph definitions#Connectedness\|SCC]]. The correspndence between the [[Basic graph definitions#Connectedness\|SCC]] and these sets of nodes is one-to-one.

	== Pseudocode ==		== Pseudocode ==

2014-10-23T15:55:53Z

← Older revision		Revision as of 15:55, 23 October 2014
Line 26:		Line 26:

	# [[Kosaraju]]		# [[Kosaraju]]

			== Further information ==
			''STRONGLY-CONNECTED-COMPONENTS'' runs in linear time.

2014-10-23T15:54:01Z

Definition

← Older revision		Revision as of 15:54, 23 October 2014
Line 1:		Line 1:
	== Definition ==		== Definition ==
	[[File:Scc.png\|300px\|thumb\|right\|Graph with marked strongly connected components]]		[[File:Scc.png\|300px\|thumb\|right\|Graph with marked strongly connected components]]
	Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path ~~fmo~~ <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.		Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path from <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

	== Input ==		== Input ==

2014-10-23T15:51:38Z

← Older revision		Revision as of 15:51, 23 October 2014
Line 10:		Line 10:

	A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.		A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.

			== Pseudocode ==

			====STRONGLY-CONNECTED-COMPONENTS(''D'')====

			<code>
			STRONGLY-CONNECTED-COMPONENTS(''D'')
			1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
			2 compute ''D''<sup>''T''</sup> (w.r.t. step 3)
			3 call '''DFS'''(''D''<sup>''T''</sup>), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
			4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
			</code>

	== Known algorithms ==		== Known algorithms ==

	# [[Kosaraju]]		# [[Kosaraju]]

2014-10-14T10:51:06Z

← Older revision		Revision as of 10:51, 14 October 2014
Line 10:		Line 10:

	A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.		A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.

			== Known algorithms ==

			# [[Kosaraju]]

2014-10-12T19:47:16Z

← Older revision		Revision as of 19:47, 12 October 2014
Line 1:		Line 1:
	== Definition ==		== Definition ==
			[[File:Scc.png\|300px\|thumb\|right\|Graph with marked strongly connected components]]
	Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path fmo <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.		Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path fmo <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

2014-10-10T12:54:03Z

Definition

← Older revision		Revision as of 12:54, 10 October 2014
Line 1:		Line 1:
	== Definition ==		== Definition ==

	Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, ~~thee~~ is path fmo <math>v</math> to <math>w</math> and a ~~üath~~ from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.		Let <math>G=(V,A)</math> be a [[Basic graph definitions\|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path fmo <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

	== Input ==		== Input ==