5. Graph Traversal.md

这一篇笔记主要讲解图遍历算法。这是一系列算法，可以统称为 whatever-first-search 。

whatever-first-search 的伪代码如下：

WhateverFirstSearch(s):
  put (null, s) into the bag
  while the bag is not empty
    take (p, v) from the bag
    if v is unmarked
      mark v
      parent(v) <- p
      for each edge vw
        put (v, w) into the bag

而使用不同的数据结构来充当 bag 可以实现不同的遍历算法：

1. stack：DFS
2. queue：BFS
3. priority-queue：Best First Search
   1. 如果 G 是无向的，并且将边的权重作为 priority，我们可以得到 s 节点的 component 的 minimum spanning tree（这个思路被用在了 Prim's Algorithm） 。
   2. 如果使用 path 的 length（边的权重和）作为 priority，我们可以得到 shortest path（这个思路被用在了 Dijkstra's Algorithm）。
   3. 如果使用 path 的 minimum weight，我们可以获得 bottleneck shortest paths（这被用在计算 maximum flow）。