Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | |||
courses:cs211:winter2012:journals:ian:chapter3 [2012/02/01 00:35] – sturdyi | courses:cs211:winter2012:journals:ian:chapter3 [2012/02/01 03:11] (current) – sturdyi | ||
---|---|---|---|
Line 4: | Line 4: | ||
* A graph is a connection of nodes and edges, which may be either directed or undirected; this can model a variety of complexes and relationships, | * A graph is a connection of nodes and edges, which may be either directed or undirected; this can model a variety of complexes and relationships, | ||
- | | + | |
* No questions. | * No questions. | ||
- | | + | |
===== 3.2 Graph Connectivity and Traversal ===== | ===== 3.2 Graph Connectivity and Traversal ===== | ||
- | * Two common patterns to algorithms answering questions about graphs are breadth-first and depth-first search; the former is particularly useful for finding shortest roots and analyzing cycles, and the latter where backtracking is easier than arbitrary jumping; both are suited to finding connected components. | + | * Two common patterns to algorithms answering questions about graphs are breadth-first and depth-first search; the former is particularly useful for finding shortest roots and analyzing cycles, and the latter where backtracking is easier than arbitrary jumping; both are suited to finding connected components. In BFS two nodes sharing an edge must be in the same layer or subsequent layers; in DFS if {// |
* No insights. | * No insights. | ||
* No questions. | * No questions. | ||
- | | + | |
===== 3.3 Implementing Graph Traversal Using Queues and Stacks ===== | ===== 3.3 Implementing Graph Traversal Using Queues and Stacks ===== |