Graph
- Trees and Hierarchical Relationships
- Trees are fantastic for representing strict hierarchical relationships.
- But not every relationship is hierarchical.
- Example: Paris Metro map.
- That is not a Tree. that contains cycles
- Trees are fantastic for representing strict hierarchical relationships.
- A graph consists of:
- A set of nodes
- A set of zero or more edges, each of which connects two nodes
- all trees are graphs
- Graph Problems
Graph Traversal
- BFS order: Act in order of distance from s.
- BFS stands for “Breadth First Search”.
- Analogous to “level order”. Search is wide, not deep.
- 0 1 24 53 68 7
- Breadth First Search
在设计算法的时候，选择适合的 Graph API 非常重要
Efficient
- DFS is worse for spindly graphs. Imagine a graph with 10000 nodes all spindly. We'll end up making 10000 recursive calls, which is bad for space.
- BFS is worse for "bushy" graphs, because our queue gets used a lot.
Find Shortest Paths
