408数据结构-图的遍历 自学知识点整理

前置知识：图的存储与基本操作

---

图的遍历是指从图的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。因为树是一种特殊的图，所以树的遍历实际上也可以视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
因为图的任意一个顶点都可能和其余的顶点相邻接，所以再访问过某个顶点后，又可能沿着某条路径搜索回到这个被访问过的结点。为了避免同一个顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，可以设一个辅助数组$visited[]$来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

广度优先搜索

知识点回顾：二叉树的层次遍历
对二叉树进行按层次的遍历，需要借助一个辅助队列实现，具体思想如下：
①首先将二叉树的根结点入队。
②若队列非空，则队头结点出队，并访问该结点。若该结点有左孩子，则将其左孩子入队；若该结点有右孩子，则将其右孩子入队。
③重复步骤②，直至队列为空。

广度优先搜索（$Breadth-First-Search,BFS$）类似于二叉树的层次遍历算法。基本思想是：首先访问起始顶点$v$，接着从$v$出发，依次访问$v$的各个未访问过的邻接顶点$w_1,w_2,\cdots ,w_i$，然后依次访问$w_1,w_2,\cdots ,w_i$的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，依此类推，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未被访问过的顶点作为起始点，再重复上述过程，直至图中所有顶点都被访问到为止。
$Dijkstra$单源最短路径算法和$Prim$最小生成树算法也应用了类似的思想。
对广度优先搜索遍历图的过程，换而言之，就是以$v$为起始点，由近至远依次访问和$v$有路径相通且路径长度为$1,2,\cdots$的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层的顶点。

代码实现

首先是预处理，包括结构体定义，基本操作函数等。因为邻接矩阵法写起来相对简单一些，所以我主要用邻接表法来写。

知识点回顾：图的邻接表存储表示法
知识点类比：二叉树的层次遍历

#define MaxVertexNum 810
typedef struct ArcNode {//边结点int adjvex;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {//顶点表结点int data;ArcNode* firstarc;
}VNode,AdjList[MaxVertexNum];
typedef struct {AdjList vertices;//邻接表存储图int vexnum, arcnum;
}ALGraph;
bool Visited[MaxVertexNum];//辅助数组标记顶点是否被访问typedef struct LinkNode {int Vertex;//图的顶点编号struct LinkNode* next;
}LinkNode;
typedef struct {LinkNode* front, * rear;//链队列
}LinkQueue;void InitQueue(LinkQueue& Q) {LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode*));p->Vertex = -1;p->next = NULL;Q.front = Q.rear = p;//初始化队列return;
}bool Q_Is_Empty(LinkQueue Q) {//队列判空return Q.front == Q.rear ? true : false;
}void EnQueue(LinkQueue& Q, int i) {//新元素入队LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode*));p->Vertex = i;p->next = NULL;Q.rear->next = p;Q.rear = p;return;
}void DeQueue(LinkQueue& Q, int& x) {//队头元素出队LinkNode* p = Q.front->next;x = p->Vertex;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front;free(p);return;
}void Visit(int i) {printf("%d ", i);return;
}

用邻接表实现广度优先搜索的代码如下：

void BFS(ALGraph& G, LinkQueue& Q, int i) {//广度优先搜索（对连通分量）Visit(i);//先访问iVisited[i] = true;EnQueue(Q, i);int v, w;//v记录队首元素，w用于临时记录访问的顶点while (!Q_Is_Empty(Q)) {//当队列不为空时DeQueue(Q, v);//队首元素出队for (ArcNode* p = G.vertices[v].firstarc; p != NULL; p = p->nextarc) {//访问v所有的邻接顶点w = p->adjvex;if (!Visited[w]) {//若顶点w未被访问过Visit(w);//访问顶点wVisited[w] = true;//对顶点w作已访问标记EnQueue(Q, w);//顶点w入队}}}return;
}void BFSTraverse(ALGraph& G, LinkQueue& Q) {//对图G进行广度优先遍历for (int i = 1; i <= G.vexnum; ++i) {Visited[i] = false;//访问标记数组初始化G.vertices[i].data = i;//其实这一步没用}InitQueue(Q);//初始化队列for (int i = 1; i <= G.vexnum; ++i)//从1号顶点开始遍历if (!Visited[i])//对每个连通分量调用一次BFS()BFS(G, Q, i);//若顶点v_i未被访问过，则从顶点v_i处开始调用BFS()return;
}

用邻接矩阵实现广度优先搜索算法如下：（并不完整，感兴趣的读者可以尝试自己写一下）

#define MaxVertexNum 114
typedef struct {int Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];int vexnum, arcnum;
}MGraph;void BFS_(MGraph& G, LinkQueue& Q, int i) {Visit(i);Visited[i] = true;EnQueue(Q, i);int v, w;while (!Q_Is_Empty(Q)) {DeQueue(Q, v);for (w = 1; w <= G.vexnum; ++w) {if (!Visited[w] && G.Edge[v][w]) {Visit(w);Visited[w] = true;EnQueue(Q, w);}}}return;
}

辅助数组$Visited[]$标志顶点是否被访问过，其初始值为$false$。在图的遍历过程中，一旦某个顶点$v_i$被访问，就立即置$Visited[i]$值为$true$，防止其被多次访问。

$BFS$算法性能分析

无论是邻接表还是邻接矩阵的存储方式，$BFS$算法都需要借助一个辅助队列$Q$，所有顶点均需入队一次，在最坏的情况下，空间复杂度为$O(|V|)$。
遍历图的过程实质上是对每个顶点查找其邻接点的过，耗费的时间取决于所采用的存储结构。
采用邻接表存储时，每个顶点均需入队一次，时间复杂度为$O(|V|)$，在搜索每个顶点的邻接点时，每条边至少访问一次，时间复杂度为$O(|E|)$。因此，总的时间复杂度为$O(|V|+|E|)$。
采用邻接矩阵存储时，查找每个顶点的邻接点所需时间为$O(|V|)$，因此，总的时间复杂度为$O(|V{|}^2)$。

$BFS$算法求解单源最短路径

若图$G=(V,E)$为无权图，定义从顶点$u$到顶点$v$的最短路径$d(u,v)$为$u$到$v$的任何路径中最少的边数；若从$u$到$v$没有通路，则$d(u,v)=\infty$。
使用$BFS$，我们可以求解一个满足上述定义的“无权图的单源最短路径问题”，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。
$BFS$算法求解单源最短路径问题的算法如下，我根据王道书上的伪代码自己稍作了一些改动：

#define INF 0x7fffffff
void BFS_MIN_Distance(ALGraph G, LinkQueue& Q, int u) {int d[MaxVertexNum], v;//d[i]表示从u到i结点的最短路径memset(d, INF, sizeof(d));//初始化路径长度为无穷大Visited[u] = true, d[u] = 0;EnQueue(Q, u);while (!Q_Is_Empty(Q)) {//BFS主过程DeQueue(Q, u);//队头出队for (ArcNode* w = G.vertices[u].firstarc; w != NULL; w = w->nextarc) {//遍历u的所有邻接点v = w->adjvex;if (!Visited[v]) {//若未访问Visited[v] = true;//标记访问d[v] = d[u] + 1;//路径长度加1EnQueue(Q, v);//顶点w入队}}}return;
}

广搜的完整代码可以看我的Github：传送门

广度优先生成树

在广度优先遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。需要注意的是，同一个图的邻接矩阵存储表示是唯一的，所以其广度优先生成树也是唯一的，但是因为邻接表存储表示不唯一，所以其广度优先生成树也不是唯一的。（广度优先遍历序列同理，因此不再展开讲）

（下图来自王道考研408数据结构课程视频的截图 - 图的广度优先遍历）

对非连通图的广度优先遍历，可以得到广度优先生成森林。其中，对每一个连通分量进行广度优先遍历得到的广度优先生成树的集合，就是这个非连通图的广度优先生成森林。
这期视频最后的思考题，我个人认为答案如下：

1. 从$1$出发，需要调用$4$次$BFS$函数，过程分别是：$1\to 5$，$2$，$3\to 6$，$4\to 7\to 8$。
2. 从$7$出发，需要调用$1$次$BFS$函数，过程是：$7\to 3\to 6\to 8\to 2\to 4\to 1\to 5$。

深度优先搜索

知识点回顾：二叉树的先序遍历
若二叉树为空，则什么也不做；否则：

• 访问根结点；
• 先序遍历左子树；
• 先序遍历右子树。

对应的递归算法如下：

void PreOrder(BiTree T) {//先序遍历（根左右）if (T != NULL) {visit(T);//访问根结点PreOrder(T->lchild);//递归访问左子树PreOrder(T->rchild);//递归访问右子树}return;
}

与广度优先搜索不同，深度优先搜索（$Depth-First-Search$，$DFS$）类似于树的先序遍历。如果其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”地搜索一个图。
它的基本思想是：首先访问图中某一起始顶点$v$，然后从$v$出发，访问与$v$邻接且未被访问的任意一个顶点$w_1$，再访问与$w_1$邻接且未被访问的任意一个顶点$w_2$……重复上述过程。当不能再继续往下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则再从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

代码实现

首先预处理，使用邻接表的方式存储图。

#define MaxVertexNum 114
typedef struct ArcNode {int adjvex;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {int data;ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {AdjList vertices;int vexnum, arcnum;
}ALGraph;bool Visited[MaxVertexNum];//访问标记数组inline void Visit(int i) {Visited[i] = true;//对i作已访问标记printf("%d ", i);return;
}

用邻接表实现深度优先搜索算法如下：

inline void DFS(ALGraph G, int i) {//注：可以不加inline，仅个人习惯Visit(i);//访问初始顶点ifor (ArcNode* p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) {//检测i的所有邻接点int j = p->adjvex;if (!Visited[j])DFS(G, j);//若j未被访问，则递归访问j}return;
}inline void DFSTraverse(ALGraph G) {for (int i = 1; i <= G.vexnum; ++i) {Visited[i] = false;//初始化访问标记数组G.vertices[i].data = i;}for (int i = 1; i <= G.vexnum; ++i) {//从1开始遍历if (!Visited[i])//若当前顶点未访问则调用DFS()DFS(G, i);}return;
}

这样写$DFSTraverse()$函数也能同时解决非连通图的遍历问题。
同样的，我也写了个不完整的邻接矩阵实现深度优先搜索算法，感兴趣的读者可以自己动手试试补全。

#define MaxVertexNum 114
typedef struct {int Vex[MaxVertexNum];int Edge[MaxVertexNum][MaxVertexNum];int vexnum, arcnum;
}MGraph;inline void DFS_(MGraph G, int i) {Visit(i);//访问初始顶点ifor (int j = 1; j <= G.vexnum; ++j) {//检查i的所有邻接点if (!Visited[j] && G.Edge[i][j])DFS_(G, j);//j为i尚未访问的邻接点，递归访问j}return;
}

深搜的完整代码可以看我的Github：传送门

$DFS$算法的性能分析

$DFS$是一个递归算法，主要空间复杂度来自递归函数工作栈，最坏情况下空间复杂度为$O(|V|)$。
遍历图的过程实质上是通过边查找邻接点的过程，因此两种遍历方式的时间复杂度都相同，不同之处仅在于对顶点的访问顺序不同。采用邻接矩阵存储时，总的时间复杂度为$O(|V{|}^2)$；采用邻接表存储时，总的时间复杂度为$O(|V|+|E|)$。

深度优先生成树和生成森林

与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用$DFS$才能产生深度优先生成树，否则产生的将是深度优先生成森林。
（下图来自王道考研408数据结构课程视频的截图 - 图的深度优先遍历）

由$2$出发，易知深度优先遍历序列为$2\to 1\to 5\to 6\to 3\to 4\to 7\to 8$。

与广度优先搜索类似，邻接矩阵生成的深度优先序列和深度优先搜索树都是唯一的；而邻接表生成的深度优先序列和深度优先搜索树都是不唯一的，具体由邻接表边表的存储顺序决定。

图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。对于无向图来说，若无向图是连通的，则从任意一个顶点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问到。对于有向图来说，若从初始顶点出发到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
因此，在$BFSTraverse()$或$DFSTraverse()$函数中，添加了第二个$for$循环，用于多次选取初始点，继续进行遍历，防止出现一次无法遍历图中所有顶点的情况。对于无向图，上述两个函数调用$BFS(G,i)$或$DFS(G,i)$的次数，等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，对非强连通分量一次调用$BFS(G,i)$或$DFS(G,i)$存在无法访问到该连通分量所有顶点的情况。

知识点回顾：图的基本概念

---

对图的遍历，408考研初试中经常在选择题里考察遍历序列和遍历生成树的问题，对代码要求不那么高。因此要结合课后习题，在充分理解概念和算法思想的基础上，重点掌握手推遍历序列的能力。
以上。