Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:bowmang:chapter3 [2018/01/30 03:11] – bowmang | courses:cs211:winter2018:journals:bowmang:chapter3 [2018/02/07 07:02] (current) – bowmang | ||
|---|---|---|---|
| Line 37: | Line 37: | ||
| * Leaf = node with no children | * Leaf = node with no children | ||
| * Every n-node tree has exactly n-1 edges | * Every n-node tree has exactly n-1 edges | ||
| + | |||
| + | ===== Chapter 3.2 (Graph Connectivity and Graph Traversal) ===== | ||
| + | |||
| + | __Maze-Solving Problem__ | ||
| + | * S-T connectivity problem (if you have a node s and a node t, is there a path between the two) | ||
| + | * Two algorithms to solve this problem are Breadth-First Search (BFS) and Depth-First Search (DFS) | ||
| + | |||
| + | __Breadth-First Search__ | ||
| + | * Algorithm ( O(n + m) ) | ||
| + | * Start with node s | ||
| + | * Add nodes one layer at a time (everything that s is connected to) | ||
| + | * Continue to add all additional nodes that are connected by an edge to any of the nodes in the first layer | ||
| + | * Repeat until no new nodes can be found. | ||
| + | * Whatever layer node t is in can determine the minimum distance between it and node s | ||
| + | * Breadth-First Search creates a tree with the root at node s | ||
| + | |||
| + | __Depth-First Search__ | ||
| + | * Algorithm ( O(n + m) ) | ||
| + | * Start with node s | ||
| + | * For each node adjacent to node s: | ||
| + | * If unexplored: | ||
| + | * Run algorithm recursively on said node | ||
| + | * | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
