Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| 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 64: | Line 64: | ||
| This method of searching explores a graph by going as deeply as possible and only retreating when necessary. | This method of searching explores a graph by going as deeply as possible and only retreating when necessary. | ||
| - | **Algorithm** | + | ==== Algorithm |
| DFS(u): | DFS(u): | ||
| mark u as " | mark u as " | ||
| 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. | 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 |
| For a given recessive call DFS(u), all nodes that are marked " | For a given recessive call DFS(u), all nodes that are marked " | ||
| with this we can prove: | 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. | 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. | ||
