Depth-first search - Revision history

Brian: /* Applications */

2012-03-03T00:28:18Z

‎Applications

Brian at 00:59, 9 April 2011

2011-04-09T00:59:59Z

Brian at 23:40, 11 March 2011

2011-03-11T23:40:33Z

Brian: /* Applications */

2011-03-11T23:03:48Z

‎Applications

Brian: formatting

2011-03-07T04:02:55Z

formatting

Show changes

Jargon: categorize

2009-12-23T17:20:28Z

categorize

Brian: /* Principles */

2009-11-18T04:52:53Z

‎Principles

Brian: /* Traversal of the spanning tree */

2009-11-18T00:02:13Z

‎Traversal of the spanning tree

Brian at 06:35, 17 November 2009

2009-11-17T06:35:01Z

Brian: /* Traversal of the spanning tree */

2009-11-17T06:22:54Z

‎Traversal of the spanning tree

@@ Line 106: / Line 106: @@
 <pre>
 function DFS(u,v)
       if id[v] = -1
            id[v] = cnt
            let pred[v] = u
@@ Line 121: / Line 121: @@
 </pre>
 After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself.
 ==References==

@@ Line 121: / Line 121: @@
 </pre>
 After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself.
 [[Category:Pages needing diagrams]]
 [[Category:Algorithms]]

@@ Line 55: / Line 55: @@
 ==The DFS tree==
 ===Undirected graphs===
-Assume we have an undirected graph consisting of a single connected component. When we run DFS on this graph, we generally consider it as a directed graph in which every edge is bidirectional. (This is akin to adding an arrowhead to each end of each edge in a diagram of the graph using circles and line segments.) Running DFS on this graph selects some of the edges (<math>|V|-1</math> of them, to be specific) to form a spanning tree. Note that these edges point generally away from the source. They are known as '''tree edges'''. When we traverse a tree link, we make a recursive call to a previously unvisited vertex. The directed edges running in the reverse direction - from a node to its parent in the DFS tree - are known as '''parent edges''', for obvious reasons. They correspond to a recursive call reaching the end of the function and returning to the caller. The remaining edges are all classified as either '''down edges''' or '''back edges'''. If a edge points from a node to one of its descendants in the spanning tree rooted at the source vertex, but it is not a tree edge, then it is a down edge; otherwise, it points to an ancestor, and if it is not a parent edge then it is a back edge. In the recursive implementation given, encountering either a down edge or a back edge results in an immediate return as the vertex has already been visited. Evidently, the reverse of a down edge is always a back edge and ''vice versa''.
+When we run DFS on an undirected graph, we generally consider it as a directed graph in which every edge is bidirectional. (This is akin to adding an arrowhead to each end of each edge in a diagram of the graph using circles and line segments.) Running DFS on this graph selects some of the edges (<math>|V|-1</math> of them, to be specific) to form the spanning tree. Note that these edges point generally away from the source. They are known as '''tree edges'''. When we traverse a tree link, we make a recursive call to a previously unvisited vertex. The directed edges running in the reverse direction - from a node to its parent in the DFS tree - are known as '''parent edges''', for obvious reasons. They correspond to a recursive call reaching the end of the function and returning to the caller. The remaining edges are all classified as either '''down edges''' or '''back edges'''. If a edge points from a node to one of its descendants in the spanning tree rooted at the source vertex, but it is not a tree edge, then it is a down edge; otherwise, it points to an ancestor, and if it is not a parent edge then it is a back edge. In the recursive implementation given, encountering either a down edge or a back edge results in an immediate return as the vertex has already been visited. Evidently, the reverse of a down edge is always a back edge and ''vice versa''.
 Every (directed) edge in the graph must be classifiable into one of the four categories: tree, parent, down, or back. To see this, suppose that the edge from node A to node B in some graph does fit into any of these categories. Then, in the spanning tree, A is neither an ancestor nor a descendant of B. This means that the lowest common ancestor of A and B in the spanning tree (which we will denote as C) is neither A nor B. Evidently, C is visited before either A or B, and A and B lie in different subtrees rooted at immediate children of C. So at some point C has been visited but none of its descendants have been visited. Now, because DFS always visits an entire subtree of the current vertex before backtracking and entering another subtree, the entire subtree containing either A or B (whichever one is visited first) must be explored before visiting the subtree containing the other. Suppose the subtree containing A is visited first. Then, when A is visited, B has not yet been visited, and thus the edge between them must be a tree edge, which is a contradiction.
@@ Line 100: / Line 101: @@
 ==Applications==
-DFS, by virtue of being a subcategory of graph search, is able to find [[Graph theory#Types of graphs|connected component]]s, paths (including [[Maximum flow|augmenting paths]]), [[Tree|spanning trees]], and [[Topological sorting|topological orderings]] in linear time. The special properties of DFS also make it uniquely suitable for finding [[biconnected component]]s (or [[bridge]]s and [[articulation point]]s) and [[strongly connected component]]s. There are three well-known algorithms for the latter, those of [[Tarjan's strongly connected components algorithm|Tarjan]], [[Kosaraju's algorithm|Kosaraju]], and [[Gabow's algorithm|Gabow]]. The [[Finding cut vertices and edges|classic algorithm]] for the former appears to have no unique name in the literature.
+DFS, by virtue of being a subcategory of graph search, is able to find [[Graph theory#Types of graphs|connected component]]s, paths (including [[Maximum flow|augmenting paths]]), [[Tree|spanning trees]], and [[Topological sorting|topological orderings]] in linear time. The special properties of DFS trees also make it uniquely suitable for finding [[biconnected component]]s (or [[bridge]]s and [[articulation point]]s) and [[strongly connected component]]s. There are three well-known algorithms for the latter, those of [[Tarjan's strongly connected components algorithm|Tarjan]], [[Kosaraju's algorithm|Kosaraju]], and [[Gabow's algorithm|Gabow]]. The [[Finding cut vertices and edges|classic algorithm]] for the former appears to have no unique name in the literature.
-The following example shows how to find connected components and a spanning forest (a collection of spanning trees, one for each connected component) with DFS.
+The following example shows how to find connected components and a DFS forest (a collection of DFS trees, one for each connected component).
 <pre>
 function DFS(u,v)

@@ Line 100: / Line 100: @@
 ==Applications==
-DFS, by virtue of being a subcategory of graph search, is able to find [[connected component]]s, paths (including [[Maximum flow|augmenting paths]]), [[Tree|spanning trees]], and [[Topological sorting|topological orderings]] in linear time. The special properties of DFS also make it uniquely suitable for finding [[biconnected component]]s (or [[bridge]]s and [[articulation point]]s) and [[strongly connected component]]s. There are three well-known algorithms for the latter, those of [[Tarjan's strongly connected components algorithm|Tarjan]], [[Kosaraju's algorithm|Kosaraju]], and [[Gabow's algorithm|Gabow]].
+DFS, by virtue of being a subcategory of graph search, is able to find [[Graph theory#Types of graphs|connected component]]s, paths (including [[Maximum flow|augmenting paths]]), [[Tree|spanning trees]], and [[Topological sorting|topological orderings]] in linear time. The special properties of DFS also make it uniquely suitable for finding [[biconnected component]]s (or [[bridge]]s and [[articulation point]]s) and [[strongly connected component]]s. There are three well-known algorithms for the latter, those of [[Tarjan's strongly connected components algorithm|Tarjan]], [[Kosaraju's algorithm|Kosaraju]], and [[Gabow's algorithm|Gabow]]. The [[Finding cut vertices and edges|classic algorithm]] for the former appears to have no unique name in the literature.
 The following example shows how to find connected components and a spanning forest (a collection of spanning trees, one for each connected component) with DFS.

← Older revision		Revision as of 17:20, 23 December 2009
Line 122:		Line 122:

	[[Category:Pages needing diagrams]]		[[Category:Pages needing diagrams]]
		+	[[Category:Algorithms]]

@@ Line 4: / Line 4: @@
 =Principles=
-DFS is distinguished from other graph search techniques in that, after visiting a vertex and adding its neighbours to the fringe, the ''next'' vertex to be visited is always the newest vertex on the fringe, so that as long as the visited vertex has unvisited neighbours, each neighbour is itself visited immediately. For example, suppose a graph consists of the vertices {1,2,3,4,5} and the edges {(1,2),(1,3),(2,4),(3,5)}. If we start by visiting 1, then we add vertices 2 and 3 to the fringe. Suppose that we visit 2 next. (2 and 3 could have been added in any order, so it doesn't really matter.) Then, 4 is placed on the fringe, which now consists of 3 and 4. Since 4 was necessarily added ''after'' 3, we visit 4 next. Finding that it has no neighbours, we visit 3, and finally 5.
+DFS is distinguished from other graph search techniques in that, after visiting a vertex and adding its neighbours to the fringe, the ''next'' vertex to be visited is always the newest vertex on the fringe, so that as long as the visited vertex has unvisited neighbours, each neighbour is itself visited immediately. For example, suppose a graph consists of the vertices {1,2,3,4,5} and the edges {(1,2),(1,3),(2,4),(3,5)}. If we start by visiting 1, then we add vertices 2 and 3 to the fringe. Suppose that we visit 2 next. (2 and 3 could have been added in any order, so it doesn't really matter.) Then, 4 is placed on the fringe, which now consists of 3 and 4. Since 4 was necessarily added ''after'' 3, we visit 4 next. Finding that it has no neighbours, we visit 3, and finally 5. It is called ''depth-first search'' because it goes as far down a path (''deep'') as possible before visiting other vertices.
 =Stack-based implementation=

@@ Line 95: / Line 95: @@
 <br/>
 Note that we do not actually know the postorder number for a vertex until after we have examined all the edges leaving it. This is not a problem for the sake of classification, since we know that any number that hasn't been assigned yet is higher than any number that has been so far assigned, and that using ∞ as a placeholder therefore doesn't change the results of comparisons. You could also use -1 as a placeholder, but you would have to modify the code somewhat.
 =Applications=

← Older revision		Revision as of 06:35, 17 November 2009
Line 117:		Line 117:
	</pre>		</pre>
	After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself.		After the termination of this algorithm, ''cnt'' will contain the total number of connected components, ''id[u]'' will contain an ID number indicating the connected component to which vertex ''u'' belongs (an integer in the range [0,''cnt'')) and ''pred[u]'' will contain the parent vertex of ''u'' in some spanning tree of the connected component to which ''u'' belongs, unless ''u'' is the first vertex visited in its component, in which case ''pred[u]'' will be ''u'' itself.
		+
		+	[[Category:Pages needing diagrams]]

@@ Line 75: / Line 75: @@
            for each v ∈ V(G) such that (u,v) ∈ E(G)
                 DFS(v)
-           let post[u] = postcnt
+           post[u] = postcnt
            postcnt = postcnt + 1
 input G