Graphs/Topological Sort - Revision history

Admin: /* Big O Cost */

2017-09-09T15:35:43Z

Big O Cost

← Older revision		Revision as of 15:35, 9 September 2017
Line 49:		Line 49:
	return topo		return topo
	</pre>		</pre>

			==Properties==

			Some interesting/useful properties of topological sort follow:

			Any vertex that is on a directed cycle will never be visited (a consequence of the fact that a vertex will only be visited if the in-degree reaches 0, implying that all predecessor nodes have already been visited). Any other vertex will be visited exactly once.

			The topological sort will either compute the topological ordering of the entire graph, or will fail to exclude some vertices that are part of a directed cycle.

	==Big O Cost==		==Big O Cost==
Line 54:		Line 62:
	A topological sort requires us to visit each node, and examine each edge at each node, for a total cost of <math>O(n+m)</math>		A topological sort requires us to visit each node, and examine each edge at each node, for a total cost of <math>O(n+m)</math>

	~~Any vertex that~~ is ~~on a directed cycle will never be visited. Any other vertex will be visited exactly once.~~		The amount of storage required by a topological sort is <math>O(n)</math> - this is the space used by the various containers (list of vertices in topological order, and in-degree counting map)

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

2017-09-09T15:20:26Z

Pseudocode

← Older revision		Revision as of 15:20, 9 September 2017
Line 49:		Line 49:
	return topo		return topo
	</pre>		</pre>

			==Big O Cost==

			A topological sort requires us to visit each node, and examine each edge at each node, for a total cost of <math>O(n+m)</math>

			Any vertex that is on a directed cycle will never be visited. Any other vertex will be visited exactly once.

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

2017-09-09T15:12:27Z

Pseudocode

← Older revision		Revision as of 15:12, 9 September 2017
Line 17:		Line 17:
	==Pseudocode==		==Pseudocode==

	The pseudocode traverses the DAG, searching for root vertices, removing them, then finding the next root vertex.		The pseudocode starts by computing the in-degree of each vertex in the DAG. it then traverses the DAG, searching for root vertices, "removing" them from the graph, decrementing the in-degree of each neighbor node, then finding the next root vertex.

	<pre>		<pre>

2017-09-09T15:11:29Z

Pseudocode

← Older revision		Revision as of 15:11, 9 September 2017
Line 16:		Line 16:

	==Pseudocode==		==Pseudocode==

			The pseudocode traverses the DAG, searching for root vertices, removing them, then finding the next root vertex.

	<pre>		<pre>
Line 28:		Line 30:
	indegree[u] = get degree of u		indegree[u] = get degree of u
	if indegree[u] is 0:		if indegree[u] is 0:
	roots~~.append(u)~~		add u to roots

	while roots is not empty:		while roots is not empty:

2017-09-09T14:48:34Z

@@ Line 3: / Line 3: @@
 To sort a graph topologically, the graph must be a directed acyclic graph (see [[DAGs]]).
 =Flags=
 {{GraphsFlag}}

2017-09-09T14:35:10Z

← Older revision		Revision as of 14:35, 9 September 2017
Line 2:		Line 2:

	To sort a graph topologically, the graph must be a directed acyclic graph (see [[DAGs]]).		To sort a graph topologically, the graph must be a directed acyclic graph (see [[DAGs]]).


			=Flags=

			{{GraphsFlag}}

2017-09-09T14:34:59Z

Created page with "=Notes= To sort a graph topologically, the graph must be a directed acyclic graph (see DAGs)."

New page

=Notes=

To sort a graph topologically, the graph must be a directed acyclic graph (see [[DAGs]]).