算法导论随笔(九)：图(Graph)的进阶与图的遍历方式(DFS, BFS)
在这篇文章中，我将介绍一些跟图有关的进阶术语，以及图的两种遍历方式，即DFS(深度优先搜索)和BFS(广度优先搜索)。对于文中使用的一些图的术语，可以读算法导论随笔(七)：图(Graph)的表示(附Python实现源码)复习一下。首先让我们来看看连通图的概念。
1. 图的连通性
在一个无向图G中，对于两个顶点u和v，若u和v之间有路径，则称u与v是连通的。如果图中任意两点都是连通的，那么图被称作连通图。
如果G是有向图，那么连接u和v的路径中所有的边都必须同向。
这种任意两个点都相同的特性叫做连通性。连通图具有连通性。
子图的概念：对于图G，其子图S具有如下属性：S的顶点集合是G的顶点集合的子集；S的边的集合是G的边的集合的子集。若S的顶点集合是G的顶点集合的真子集，且S的边的集合是G的边的集合的真子集，则称S是G的真子图。
极大子图：若P是G的子图，而且P不是G的任何其他的子图的真子图，则P是G的极大子图。
连通分量：若一个图G的极大子图P是连通图，则P是G的连通分量。对于一个连通图来说，它的连通分量为其自身；对于非连通图来说，它可能有多个连通分量。
例如下面的图，它不是连通图，因此有两个连通分量，分别用红色和蓝色标出。
接着，让我们来看看一个进阶概念。
2.双连通图
在了解双连通图(Biconnected Graph)的概念之前，让我们先了解一下分离边(separation edges)和分离顶点(Separation vertices)的概念。
首先，在一个图中，若删除一个顶点及与该顶点相邻的边会把这个图分裂为两个互不相连的图（也就是破坏了其连通性），则该顶点称为分离顶点。
类似地，在一个图中，若删除一条边会导致这个图被分裂为两个互不相连的图，则该边称为分离边。
例如下图中，顶点LGA，DFW和LAX是三个分离顶点，而红色的这条边是一条分离边。
于是我们可以得到对双连通图的如下定义：
定义一：若一个图G中不含有任何分离顶点或分离边，则G为连通图。下图就是一个双连通图。
对于连通图，还有如下两个等效定义。也就是说，用定义一、定义二和定义三，都可以定义出一个双连通图。
定义二：若一个图G中，在任意两个顶点u和v之间，都有两个不同的简单路径，则G为双连通图。
例如，对于上图中的SFO和LGA两个顶点，有两个不同的简单路径：(SFO, ORD), (ORD, LGA)以及(SFO, LAX), (LAX, DFW), (DFW, LGA)。对于图中任意两个顶点，我们都能找到两个不同的简单路径。
定义三：若一个图G中，对于任意两个顶点u和v，都存在一个简单循环中包含u和v，则G为双连通图。
例如顶点SFO和LGA都被简单循环(SFO, LAX), (LAX, DFW), (DFW, LGA), (LGA, ORD)所包含。如下图。
3. 双连通分量
了解了双连通图的概念之后，再来看看双连通分量(Biconnected components)的概念。双连通分量并不独立存在，它依赖于图。可以把它看成一个图的双连通子图。
对于一个图G，它的双联通分量P可以这样定义：
P是G的一个双连通的极大子图，或者
P是G的一个子图，并且P包含了G中的一条分离边和该条边的两个端点。
例如下图中的图有4个双连通分量。每一个双联通分量，单独看都是一个双联通图。大家可以自己根据定义来验证一下。
双连通分量有以下特征：
- 一条边只能属于一个双连通分量；
- 若一个顶点不是分离顶点，则它只能属于一个双连通分量。
- 若一个顶点是分离顶点，则它至少同时属于两个双连通分量。
例如上图中LAX，DFW和LGA都是分离顶点，它们均被两个双连通分量所包含。其他顶点都只属于一个双连通分量。图中任意一条边都只属于一个双连通分量。
4. 图的遍历之DFS(深度原先搜索)
图的遍历是指访问图的每一个顶点。下面来看图的遍历方式的一种，即深度优先搜索(depth-first search)。该方式的主旨是，在访问了一个顶点P及该顶点的其中一个邻接点Q之后，接下来访问的是Q的邻接点。
与之相对的就是广度优先搜索(breadth-first search)，也叫宽度优先搜索。广度优先搜索的主旨是，在访问了一个顶点P及该顶点的其中一个邻接点Q之后，接下来访问的是P的另一个邻接点。所谓“宽度”，指的就是要先访问完P的所有邻接点，再访问其他顶点。
下面来看深度优先搜索的伪代码。
该算法的输入为一个图G和一个G中的一个顶点v。v即是算法开始的顶点。
算法输出该图的最大连通分量，该分量中包含了探索的边、回退的边以及探索的顶点。在算法进行过程中，若一条边两个顶点都已经被访问过，则这条边标为回退的边。
该算法的例子如下。假设下图中A为开始的顶点。
注意：图中红色带箭头的实线表示已探索的边；红色边框顶点为已探索的顶点；蓝色的实线代表尚未探索过的边；蓝色边框的顶点为尚未探索过的顶点；绿色虚线表示回退的边。
第一步：
第二步：
第三步：注意，此步骤产生了回退的边，因为C和A都已被访问过。
第四步：
第五步：
第六步：
5. 图的遍历之BFS(广度原先搜索)
广度优先搜索的伪代码如下。
该算法的输入为一个图G和一个G中的一个顶点v。v即是算法开始的顶点。
算法输出该图的最大连通分量，该分量中包含了探索的边、交叉的边(本质上与DFS中回退的边相同)以及探索的顶点。
算法将图中的顶点分层：输入的顶点v为第0层；v的所有邻接点为第一层；每个邻接点的邻接点为第二层，以此类推。对于每一层的顶点，都有一个列表来纪录改层的顶点。
以下图为例。
注意：图中红色带箭头的实线表示已探索的边；红色边框顶点为已探索的顶点；蓝色的实线代表尚未探索过的边；蓝色边框的顶点为尚未探索过的顶点；绿色虚线表示交叉的边。图中L0，L1和L2表示每一层的列表。可以看出，只有当每一层的节点被访问完毕时，才会访问下一层的节点，这样一层一层横着访问，即是“广度优先”。
第一步：
第二步：
第三步：
第四步：
第五步：
第六步：
第七步：
6.写在最后
下面来分析一下两个算法的复杂度。其实我们可以看出，不论该算法的代码有多花哨，归根结底它访问了图中所有的节点和边。而访问任何一个点或一条边的复杂度都是O(1)。因此，两种算法的复杂度都只与顶点数量|V|和边数量|E|有关。因此。两种算法的复杂度都是
深度优先搜索和广度优先搜索不止可以对图作遍历，也可以对树作遍历。实际上，图和树非常相似，唯一区别就是，图有循环(cycle)，而树没有。
对于这两种算法的应用，可以在我的另两篇文章中找到。
人工智能: 自动寻路算法实现(一、广度优先搜索)
人工智能: 自动寻路算法实现(二、深度优先搜索)