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

  • 有向/无向图的深/广度搜索-以及最短路径

  • 源码: 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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # 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 .直到堆栈为空.
  • 这里的堆栈可以设计使用程序的递归栈,不必自行维护.

  • 示例

    • DFS.gif
  • 算法复杂度

    • 空间复杂度: 因为需要自行维护一个堆栈,堆栈的最大长度 < 顶点个数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)

  • BFS.gif

  • 算法复杂度

    • 空间复杂度: 与 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}$ 为 BFS 搜索过程中队列的一个状态,有 $v_r.d \leq v_1.d + 1$,且有 $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 下相同.

结语

  • 下一节是连通分量/拓扑排序/符号图等