Differences

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

--- courses:cs211:winter2014:journals:emily:entrythree [2014/01/29 01:41] – [Breadth-First Search] hardye
+++ courses:cs211:winter2014:journals:emily:entrythree [2014/02/10 18:42] (current) – [Depth-First Search] hardye
@@ Line 38: / Line 38: @@
 =====Breadth-First Search=====
 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. \\
-**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 56: / Line 58: @@
+=== Theorem 3.5 ===
+The set R produced at the end of the algorithm is precisely the connected component of G containing s.
+===== Depth-First Search =====
+This method of searching explores a graph by going as deeply as possible and only retreating when necessary.
+==== Algorithm ====
+    DFS(u):
+       mark u as "Explored" and add u to R
+       For each edge (u,v) incident to u
+          If v is not marked "Explored" then
+             Recursively invoke DFS(v)
+          Endif
+       Endfor
+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 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 ====
+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.
+This chapter was very readable: 9, but I feel like it did not talk about the run-time of the algorithms and the similarities and differences between the two different searches. One question I have is why is adding to the stack O(2m)?
 ====== Chapter 3.3 ======
+**Implementing Graph Traversal Using Queues and Stacks**
+In this chapter we discuss how to actually use lists and arrays to represent graphs.
+To represent a graph you can use either an adjacency matrix or an adjacency list. We implement the search algorithms in O(m+n) time which we refer to as linear. The adjacency matrix lets us check if there is a connection between a given edge in constant time BUT it takes up Θ(n<sup>2<\sup>) space and checking all the edges can take Θ(n) time. The adjacency list is better for more sparse graphs and requires only O(m+n) space.
+**Queues and Stacks**
+In BFS and DFS it is important how each node is visited and in what order. BFS -> Queue = LIFO. DFS -> Stack = FIFO.
+BFS doesn't matter whether you use a queue or a stack because the algorithm considered the nodes in a layer in any order. BFS can use a queue to process nodes in the way they were first discovered and can do this in O(m+n) time.
+DFS uses a stack to implement the algorithm because the algorithm finds the farthest node and then retreats as soon as it has gone as far as it can. The implementation of the algorithm runs in O(m+n) time as well.
+This chapter was not as easy to follow in class simply because we were following the algorithms step by step. I'm glad I read after the information was presented in class because it made it easier to understand. Readability 7.