5.1 Graph traversal、spanning tree 与 shortest path

Graph 用来表示不自然排成直线的关系。进入 graph 后，最重要的是分清 abstract object 和 representation，再按问题选 traversal 或 optimization method。

Graph vocabulary

Directed edge 有方向，(u, v) 不等于 (v, u)。Weighted edge 有 cost、 distance 或 capacity。这些特征会改变可用 algorithm。

Lecture 还区分 path、simple path、cycle、acyclic graph、connectivity 和 degree。这些词会决定 algorithm 是否适用。

Representations

常见 representation 有 adjacency matrix 和 adjacency list。

• Adjacency matrix 查 edge 很直接，但 space 与 vertices 数平方有关。
• Adjacency list 储存每个 vertex 的 neighbors，对 sparse graph 较自然。

分析 graph algorithms 时，要说明 representation，或者用 $V$ 和 $E$ 表示成本。

Depth first search

DFS 会沿一条 branch 尽量深入，不能再走才 backtrack。Tutorial 用 current stack 和 visited array 追踪这件事。

DFS 常用于 reachability、connected components、cycle reasoning，以及 DFS-based topological sorting。

Breadth first search

BFS 按距离 layer visit vertices。Tutorial 用 queue，而不是 stack。

在 unweighted graph 中，BFS 给出用 edge 数量衡量的 shortest path distance； DFS 不保证这点。

Minimum spanning trees

对 connected undirected weighted graph，spanning tree 包含所有 vertices 和 刚好 $V - 1$ 条 edges。Minimum spanning tree 令 total edge weight 最小。

Kruskal's algorithm 先按 edge weight 排序，逐条加入不会形成 cycle 的最轻 edge。Prim's algorithm 则由一棵 tree 开始，每次加入连到新 vertex 的最轻 edge。

Dijkstra-style shortest paths

Dijkstra 解另一个问题：在 nonnegative weighted graph 中，由一个 start vertex 到其他 vertices 的 shortest paths。它保存每个 vertex 的 current best cost， 每次 finalize current cost 最小的 unvisited vertex，然后 relax 它的 outgoing edges。

Visited 的意思很强：一个 vertex finalized 后，到它的 shortest path 已经确定。

练习

1. 解释何时 adjacency list 比 adjacency matrix 更合适。
2. 解释为什么 BFS 在 unweighted graph 中给出 shortest paths。
3. 分清 MST problem 和 single-source shortest path problem。