Differences

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

--- courses:cs211:winter2014:journals:emily:entrythree [2014/02/10 18:16] – [(3.4) Theorem] 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.\\
 BFS produces a tree whose root is node s. \\
-== (3.4) Theorem ==
+=== Theorem 3.4 ===
 Let T be a BFS tree, let x and y be nodes in T belonging to layers L<sub>i</sub> and L<sub>j</sub> respectively, an let (x,y) be an edge of G. Then i and j differ by at most 1.
 To explore a connected component we refer to the set R of nodes that are reachable from s.
-**Algorithm**
+=== Algorithm ===
     R will consist of nodes to which s has a path
     Initially R = {s}
@@ Line 58: / Line 57: @@
     Endwhile
-**Theorem 3.5**
+=== Theorem 3.5 ===
 The set R produced at the end of the algorithm is precisely the connected component of G containing s.
@@ 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.