数据结构-图(二)深度广度搜索-最短路径

发表于 2019-05-31 分类于计算机基础，数据结构阅读次数： Disqus：本文字数： 2.9k 阅读时长 ≈ 3 分钟

有向/无向图的深/广度搜索-以及最短路径
源码: https://github.com/Jasper-1024/python/tree/master/data_structure/Graph
更新
1
2
19.05.31 初始
19.06.04 补完

参考资料
算法第四版,算法导论.

导语

图搜索部分除了深度/广度搜索外还有不少东西,这里先写完深度/广度搜索,连通分量/拓扑排序/符号图等放在下节.
本章是深度/广度搜索的概念以及最短路径.

搜索

定义 Search 和 Path 的 API
分别在 DFS 与 BFS 内实现 Path.

API

# Search base class
class Search(object):
    # find all vertices connected to s
    def search(self, Graph, s: int = 0):
        pass

    # return whether s and v connect
    def marked(self, v: int = 0) -> bool:
        return False

    # return the number  of all vertices connected to s
    def count(self) -> int:
        return 0


# Path base class
class Paths(object):
    # find all path which began with s
    def paths(self, Graph, s: int = 0):
        pass

    # whether v and s has path
    def hasPathTo(self, v: int = 0) -> bool:
        return False

    # retuen path between s and v ,if not exist return null
    def pathTo(self, v: int = 0):
        return None

深度优先搜索

深度优先搜索（Depth-First-Search，DFS）是图论中一种非常经典的算法也是与拓扑排序有关问题的基础.
DFS 的思想非常简单沿着一条路走到黑,直到不能再继续前行,转而折返到最近的叉路口,继续走到黑,这样进行直到搜索完全部可搜索范围.
步骤(遍历一个图节点连通分量过程)
- 将根节点放入一个堆栈
- 不断将栈顶元素的下一个未标记节点压入堆栈.并标记该节点.直到找不到新的未标记节点.
- 不断弹出栈顶元素,直到找到栈顶元素存在下一个未标记节点.重复 1 2 .直到堆栈为空.
这里的堆栈可以设计使用程序的递归栈,不必自行维护.
示例
算法复杂度
- 空间复杂度: 因为需要自行维护一个堆栈,堆栈的最大长度 < 顶点个数V.所以空间复杂度为 $O(V)$ .当使用递归实现时,空间复杂度也为 $O(V)$ .
- 时间复杂度(数据结构有关,以邻接表为例)
  - 查找一个顶点临近节点的时间复杂度为 $O(E)$ .
  - 查找每个顶点的时间复杂度为 $O(V)$
  - 所以总的时间复杂度为 $O(V+E)$
路径问题(图 $G = (V,E)$ 有/无向图,由节点s开始搜索)
- 这里我们维护一个 edgeTo[] 数组,记录 DFS 的遍历路径.
- 例如 edgeTo[2] = 1 ,代表顶点 2 在 DFS 下的上一个定点为 1 .
- 实现 pathTo 只需要沿着 edgeTo[v] 回溯.

广度优先搜索

广度优先搜索算法（Breadth-First-Search，BFS）, BFS 是处理图的另一类问题的基础,例如: 最小生成树,单源最短路径等.
BFS是由根节点开始,按照距离根节点远近,一层一层的访问,直到所有连通节点都被访问.
步骤:
- 根节点加入队列并标记.
- 将队列头元素出队,将其所有相邻未标记节点入队.
- 重复直到队列为空
这里如果用 python 实现,最好使用 deque,而不是一个 list (list实现删除头元素,需要重排整个list)
算法复杂度
- 空间复杂度: 与 DFS 相同,都是 $O(V)$ , 主要取决与队列的长度.
- 时间复杂度(与数据结构相关,这里是邻接链表):
  - 每个节点最多入队一次.这样扫描所有节点的时间复杂度为 $O(V)$
  - BFS 只在每个节点出队时候,对邻接链表扫描,且每个链表只扫描一次.扫描链表的时间复杂度为 $O(E)$
  - 所以总的时间复杂度为 $O(V+E)$ .
路径问题(图 $G = (V,E)$ 有/无向图,由节点s开始搜索)
- 在搜索结束时,对所有的与 s 连通的节点 v,s 到 v 的距离 v.d 就是 $\delta (s,v)$ 即 s-v 的最短路径.
- 算法导论的证明有点绕,这里尝试换个角度.
  - 引论
    - 对于边 (u,v) 而言,s 为 G 的任意节点,有 $\delta (s,v) \leq \delta (s,u) + 1$
    - 假设 ${v_1,v_2,...,v_r}$ $v_{1}, v_{2}, . . ., v_{r}$ 为 BFS 搜索过程中队列的一个状态,有 $v_r.d \leq v_1.d + 1$ $v_{r} . d \leq v_{1} . d + 1$ ,且有 $v_i.d \leq v_{i+1}.d$ $v_{i} . d \leq v_{i + 1} . d$ .换一种说法就是在队列中节点与s距离只有 d 和 d+1 两个值,d 是逐步+1增长的,直到与s距离最远的节点入队为止.
      - 对于初始状态下结论显然成立.
      - 节点出队时,结论依旧成立.
      - 节点 a 入队时,队尾的节点 b 有两种情况,1, $a.d = b.d$ ,a与b在同一个邻接链表. 2, $a.d = b.d + 1$ ,在BFS顺序下,a在b的邻接链表中. 这两种情况下,结论依旧成立.
  - 归纳法
    - 在 d=0 的时候,队列中只有 s 节点,结论显然成立.
    - 设 u 是 v 在 BFS 下的前驱节点, $v.d = u.d + 1$ . 设对于节点 u ,结论成立,则有 $u.d = \delta (s,u)$ .
    - 假设结论对 v 不成立,则有 $\delta (s,v) < v.d$ .
    - 根据引论1可得, $\delta (s,v) \leq \delta (s,u) + 1$ ,由引论2与前提可知结论在距离 s 为 d 及 < d 的节点都成立,则 $\delta (s,v) > u.d$ 则 $\delta (s,v) \geq u.d + 1$ ,由此可以得出 $\delta (s,v) = \delta (s,u) + 1 = v.d$ 与假设结论矛盾,故假设不成立.在结论对 u 成立的前提下,结论对 v 成立.
- 对于路径的记录这里同样引入 edgeTo[] .求解具体路径与 DFS 下相同.

导语

搜索

深度优先搜索

广度优先搜索

结语