图遍历算法

DFS和BFS是最基础的图遍历算法，不论在图算法邻域还是其他各个邻域都极其重要，例如DFS中的搜索思想也是人工智能的基础。很多文章都对于DFS和BFS的直观理解做了很多解释，但对于DFS和BFS的重要性质却不够详细，因此本文主要总结了DFS和BFS的一些重要性质。

DFS（深度优先遍历）

算法介绍

类似于探索与回溯的过程

性质

下面是一些DFS相关的性质，其中性质1、4对于证明DFS的复杂度至关重要，而性质2、3分别定义了DFS树、DFS序等伴随着DFS的重要结构、属性，揭示DFS的本质。

性质1

每个结点恰被访问一次。

证明：每个结点访问后被标记为已访问，避免再次访问。

性质2：DFS树

DFS算法可构成DFS树。

DFS算法在一个结点的所有邻居都被访问过的时候沿着进入该节点的边回退该节点，这些边组成的集合构成了一颗树。

证明：由于每个结点均被回退一次（根节点除外），故上述定义下的边集和结点集合一一对应，且连接了所有结点，满足树的定义。

性质3：DFS序

DFS同时伴随着每个结点初次访问的起始时间戳，该时间戳可定义为每个结点的DFS序。类似地，也可以定义每个结点结束访问（回退）的时间戳。这两个时间戳指明了结点的不同关系，也与DFS树密切相关。

例如：在DFS树中，祖先结点的起始时间戳一定小于子孙结点的起始时间戳；相反地，祖先结点的结束时间戳一定大于子孙结点的结束时间戳。证明较显然，从略。

对于回溯边（DFS树中的非树边）等的时间戳，也有类似地性质，此处从略。

性质4

每条边最多被访问2次。

证明：DFS算法中的边有两种，一种包含在DFS树中，一种不包含。也即由DFS树所定义的的树边和非树边。对于树边，在前进和回退的过程中均被访问，故被访问两次；对于非树边，将仅沿着DFS序小的结点指向DFS序大的结点被访问1次。

综上，DFS中每条边至多被访问2次。

时间复杂度

DFS的复杂度为$O(E)$

证明：DFS的复杂度由两部分组成

• 访问结点
• 访问边

根据性质1，每个结点最多被访问1次, 因此访问结点的总时间复杂度为$O(V)$

同理，根据性质4，访问边的总时间复杂度为$O(E)$

综上，DFS的复杂度为$O(E)$

BFS（广度优先遍历）

算法介绍

不同于DFS的探索与回溯，每次遇到一个新的路口就走进去尝试；BFS遍历类似于分身走迷宫，每次遇到岔路口将自己分身，同时走入几个新的路口。DFS借助递归实现，本质表现为栈的特点，而BFS借助队列实现。

性质

性质1

BFS中每个结点恰被访问1次，证明从略。

性质2：BFS序与最短路径

BFS本质为一种层次遍历，源点（起始点）$S$的层次为0，然后访问$S$的所有未被访问的邻居，置其层次为1，然后不断访问层次为1的结点的未被访问的邻居，置其层次为2…

从BFS的流程，可以根据上面的“层次”定义BFS序，其中任一结点$u$的BFS序本质为$S$到$u$的最短路径长度。

证明：用归纳法，较为显然，从略

性质3：BFS层次图

根据BFS序定义，将层次低的结点与层次高的结点之间连接一条有向边，构成了BFS层次图。

BFS层次图为DAG（有向无环图）

证明：反证法，若层次图中有环显然违背序的大小传递性，矛盾。

性质4

BFS中每条边恰被访问1次。

证明：与DFS的证明类似，但不同的是BFS的流程中因为没有DFS中回退的过程，BFS中所有的边都恰好仅被访问1次。

时间复杂度

BFS的复杂度为$O(E)$

证明：与DFS类似，BFS的复杂度也由两部分组成

• 访问结点
• 访问边

根据性质1，每个结点最多被访问1次, 因此访问结点的总时间复杂度为$O(V)$

同理，根据性质4，访问边的总时间复杂度为$O(E)$

综上，BFS的复杂度也为$O(E)$