Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revisionNext revisionBoth sides next revision | ||
| courses:cs211:winter2012:journals:carrie:ch3 [2012/01/30 02:02] – created hopkinsc | courses:cs211:winter2012:journals:carrie:ch3 [2012/01/30 03:42] – hopkinsc | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Chapter 3 ====== | ====== Chapter 3 ====== | ||
| - | ==== 3.1 ==== | + | |
| + | ====== 3.1 Basic Definitions and Applications ====== | ||
| Definitions, | Definitions, | ||
| Line 27: | Line 29: | ||
| * G has n - 1 edges. | * G has n - 1 edges. | ||
| * There is a mistake in the above thm written on pg 78. (on instead of). also can't I just use this theorem to prove the one in our home work set? | * There is a mistake in the above thm written on pg 78. (on instead of). also can't I just use this theorem to prove the one in our home work set? | ||
| + | |||
| + | ====== 3.2 Graph Connectivity and Graph Traversal ====== | ||
| + | Already learned what it means to be connected - now looking at what we can do with that | ||
| + | |||
| + | Breadth First Search | ||
| + | * Looks at one node then all the nodes attached to it then all the nodes attached to each of those new nodes, goes by layers | ||
| + | * layer represents how far it is from root node, (also node in layer 5 is two away from node in layer three etc) | ||
| + | * can find shortest path with BFS | ||
| + | |||
| + | Theorem 3.3 | ||
| + | * for each j >= 1, Lj produuced by BFS consists of all nodes at exactly j distance from s. There is a path from s to t if and only if tappears in some layer. | ||
| + | |||
