Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:emily:entrythree [2014/02/10 18:40] – [Fact] hardye
+++ courses:cs211:winter2014:journals:emily:entrythree [2014/02/10 18:42] (current) – [Depth-First Search] hardye
@@ Line 39: / Line 39: @@
 This search is exploring the nodes outward in all possible directions, //layer by layer//. Layer L<sub>1</sub> has all nodes that are direct neighbors of S. Layer L<sub>i+1</sub> has all nodes that don't belong to an earlier layer and have an edge to a node and layer L<sub>i</sub>. The layer number (j) is the distance exactly from a node in that layer to the target node, s. \\
-==== Fact ====
+=== Fact ===
 For each i>=1, layer L<sub>i</sub> produced by BFS consists of all nodes at a distance exactly j from s. There is a path from s to t iff t appears in some layer.\\
@@ Line 64: / Line 64: @@
 This method of searching explores a graph by going as deeply as possible and only retreating when necessary.
-**Algorithm**
+==== Algorithm ====
     DFS(u):
        mark u as "Explored" and add u to R
@@ Line 75: / Line 75: @@
 BFS is similar in that it builds the connected component containing s and they achieve the same level of efficiency. But DFS visits the same number of nodes in a completely different order. DFS trees have a greater height and are narrower.
-**Theorem**
+==== Theorem 3.6 ====
 For a given recessive call DFS(u), all nodes that are marked "Explored" between the invocation and end of the this recursive call are descendants of u in T.
 with this we can prove:
-**Theorem 3.7**
+==== Theorem 3.7 ====
 Let T be a depth first search tree, let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.