🔥 本文由 程序喵正在路上 原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：2022年11月16日
🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
🌟 一以贯之的努力 不得懈怠的人生

阅读指南

• 基本操作
• 广度优先遍历（BFS）
• • 与树的广度优先遍历之间的联系
  • 算法实现
  • 复杂度分析
  • 广度优先生成树
• 深度优先遍历（DFS）
• • 与树的深度优先遍历之间的联系
  • 算法实现
  • 复杂度分析
  • 深度优先遍历序列
  • 深度优先生成树
  • 图的遍历和图的连通性

基本操作

• Adjacent(G,x,y)Adjacent(G, x, y)Adjacent(G,x,y)：判断图 GGG 是否存在边 或 (x,y)(x, y)(x,y)
• Neighbors(G,x)Neighbors(G, x)Neighbors(G,x)：列出图 GGG 中与结点 xxx 邻接的边
• InsertVertex(G,x)InsertVertex(G, x)InsertVertex(G,x)：在图 GGG 中插入顶点 xxx
• DeleteVertex(G,x)DeleteVertex(G, x)DeleteVertex(G,x)：在图 GGG 中删除顶点 xxx
• AddEdge(G,x,y)AddEdge(G, x, y)AddEdge(G,x,y)：若无向边 (x,y)(x, y)(x,y) 或有向边 不存在，则向图 GGG 中添加该边
• RemoveEdge(G,x,y)RemoveEdge(G, x, y)RemoveEdge(G,x,y)：若无向边 (x,y)(x, y)(x,y) 或有向边 存在，则从图 GGG 中删除该边
• FirstNeighbor(G,x)FirstNeighbor(G, x)FirstNeighbor(G,x)：求图 GGG 中顶点 xxx 的第一个邻接点，若有则返回顶点号；若 xxx 没有邻接点或图中不存在 xxx，则返回 −1-1−1
• NextNeighbor(G,x,y)NextNeighbor(G, x, y)NextNeighbor(G,x,y)：假设图 GGG 中顶点 yyy 是顶点 xxx 的一个邻接点，返回除了 yyy 之外顶点 xxx 的下一个邻接点的顶点号，若 yyy 是 xxx 的最后一个邻接点，则返回 −1-1−1
• Getedgevalue(G,x,y)Get_edge_value(G, x, y)Gete​dgev​alue(G,x,y)：获取图 GGG 中边 (x,y)(x, y)(x,y) 或 对应的权值
• Setedgevalue(G,x,y,v)Set_edge_value(G, x, y, v)Sete​dgev​alue(G,x,y,v)：设置图 GGG 中边 (x,y)(x, y)(x,y) 或 对应的权值为 vvv

广度优先遍历（BFS）

与树的广度优先遍历之间的联系

树的广度优先遍历，也就是树的层次遍历，有以下步骤：

1. 若树非空，则根节点入队
2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
3. 重复第 222 步指导队列为空

对于树，由于树不存在 “回路”，因此在搜索相邻的结点时，不可能搜索到已经访问过的结点；而图则反之，所以我们需要对图中的结点进行标记，以此来识别这个结点是否访问过

广度优先遍历（Breadth−First−Search,BFSBreadth-First-Search, BFSBreadth−First−Search,BFS）要点：

1. 找到与一个顶点相邻的所有顶点
2. 标记哪些顶点被访问过
3. 需要一个辅助队列

在广度优先遍历中，我们需要用到两个基本操作：

• FirstNeighbor(G,x)FirstNeighbor(G, x)FirstNeighbor(G,x)：求图 GGG 中顶点 xxx 的第一个邻接点，若有则返回顶点号；若 xxx 没有邻接点或图中不存在 xxx，则返回 −1-1−1
• NextNeighbor(G,x,y)NextNeighbor(G, x, y)NextNeighbor(G,x,y)：假设图 GGG 中顶点 yyy 是顶点 xxx 的一个邻接点，返回除了 yyy 之外顶点 xxx 的下一个邻接点的顶点号，若 yyy 是 xxx 的最后一个邻接点，则返回 −1-1−1

算法实现

bool visited[MAX_VERTEX_NUM];	//访问标记数组，初始值都为falsevoid BFSTraverse(Graph G) {		//对图G进行广度优先遍历for (i = 0; i < G.vexnum; ++i) {visited[i] = false;		//访问标记数组初始化}InitQueue(Q);				//初始化辅助队列Qfor (i = 0; i < G.vexnum; ++i) {	//从0号顶点开始遍历if (!visited[i]) 				//对每个连通分量调用一次BFSBFS(G, i);					//vi未访问过，从vi开始BFS}
}//广度优先遍历
void BFS(Graph G, int v) {		//从顶点v出发，广度优先遍历图visit(v);					//访问初始顶点vvisited[v] = true;			//对v做已访问标记Enqueue(Q, v);				//顶点v入队列Qwhile (!isEmpty(Q)) {DeQueue(Q, v);			//顶点v出队for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {//检测v所有邻接点if (!visited[w]) {				//w为v的未访问过的邻接顶点visit(w);					//访问顶点wvisited[w] = true;			//对w做已访问标记Enqueue(Q, w);				//顶点w入队列Q}//if}//for}//while
}	

结论：对于无向图，调用 BFSBFSBFS 函数的次数 === 连通分量数（连通分量：一个极大连通子图为一个连通分量）

复杂度分析

空间复杂度：

• 最坏情况，我们访问第一个顶点时，所有顶点都和它连通，此时辅助队列大小为 O(∣V∣)O(|V|)O(∣V∣)

如果我们是用邻接矩阵存储的图：

• 访问 ∣V∣|V|∣V∣ 个顶点需要 O(∣V∣)O(|V|)O(∣V∣) 的时间
• 查找每个顶点的邻接点都需要 O(∣V∣)O(|V|)O(∣V∣) 的时间，而总共有 ∣V∣|V|∣V∣ 个顶点
• 时间复杂度 =O(∣V∣2)= O(|V|^2)=O(∣V∣2)

如果我们是用邻接表存储的图：

• 访问 ∣V∣|V|∣V∣ 个顶点需要 O(∣V∣)O(|V|)O(∣V∣) 的时间
• 查找每个顶点的邻接点共需要 O(∣E∣)O(|E|)O(∣E∣) 的时间
• 时间复杂度 =O(∣V∣+∣E∣)= O(|V| + |E|)=O(∣V∣+∣E∣)

广度优先生成树

广度优先生成树由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一

对于非连通图的广度优先遍历，我们还可以得到广度优先生成森林

深度优先遍历（DFS）

与树的深度优先遍历之间的联系

树的深度优先遍历分为先根遍历和后根遍历，图的深度优先遍历和树的先根遍历比较相似

//树的先根遍历
void PreOrder(TreeNode *R) {if (R != NULL) {visit(R);		//访问根节点while (R还有下一个子树T)PreOrder(T);	//先根遍历下一棵子树}
}

算法实现

bool visited[MAX_VERTEX_NUM];	//访问标记数组void DFSTraverse(Graph G) {				//对图G进行深度优先遍历for (v = 0; v < G.vexnum; ++v)		//初始化已访问标记数据visited[v] = false;for (v = 0; v < G.vexnuj; ++v)		//解决非连通图无法遍历完的问题if (!visited[v]) DFS(G, v);
}void DFS(Graph G, int v) {		//从顶点v出发，深度优先遍历图Gvisit(v);					//访问顶点vvisited[v] = true;			//设置已访问标记for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {if (!visited[w]) {		//w为v的未访问的邻接顶点DFS(G, w);}}
}

复杂度分析

空间复杂度：来自函数调用栈，最坏情况下，递归深度为 O(∣V∣)O(|V|)O(∣V∣)；最好情况为 O(1)O(1)O(1)

时间复杂度 === 访问每个节点所需时间 +++ 探索每条边所需时间

如果是用邻接矩阵存储的图：

• 访问 ∣V∣|V|∣V∣ 个顶点需要 O(∣V∣)O(|V|)O(∣V∣) 的时间
• 查找每个顶点的邻接点都需要 O(∣V∣)O(|V|)O(∣V∣) 的时间，总共有 ∣V∣|V|∣V∣ 个顶点
• 总时间复杂度为 O(∣V∣2)O(|V|^2)O(∣V∣2)

如果是用邻接表存储的图：

• 访问 ∣V∣|V|∣V∣ 个顶点需要 O(∣V∣)O(|V|)O(∣V∣) 的时间
• 查找每个顶点的邻接点共需要 O(∣E∣)O(|E|)O(∣E∣) 的时间
• 时间复杂度 =O(∣V∣+∣E∣)= O(|V| + |E|)=O(∣V∣+∣E∣)

你会发现，深度优先遍历和广度优先遍历的复杂度是一样的

深度优先遍历序列

对于上图：

• 从 111 出发的深度优先遍历序列为：1,2,6,3,4,7,8,51, 2, 6, 3, 4, 7, 8, 51,2,6,3,4,7,8,5
• 从 222 出发的深度优先遍历序列为：2,1,5,6,3,4,7,82, 1, 5, 6, 3, 4, 7, 82,1,5,6,3,4,7,8
• 从 333 出发的深度优先遍历序列为：3,4,7,6,2,1,5,83, 4, 7, 6, 2, 1, 5, 83,4,7,6,2,1,5,8

注意：如果邻接表不一样，深度优先遍历序列也可能不一样；同时，因为邻接矩阵表示方式唯一，所以深度优先遍历序列唯一

深度优先生成树

将深度优先遍历序列写成树的形式，即为对应的深度优先生成树

如果是非连通图，那么会有深度优先生成森林

图的遍历和图的连通性

对无向图进行 BFS/DFSBFS/DFSBFS/DFS 遍历，调用 BFS/DFSBFS/DFSBFS/DFS 函数的次数等于连通分量数；如果是连通图的话，我们只需要调用一次 BFS/DFSBFS/DFSBFS/DFS 函数

对有向图进行 BFS/DFSBFS/DFSBFS/DFS 遍历，调用 BFS/DFSBFS/DFSBFS/DFS 函数的次数要根据具体的数进行具体分析；如果起始顶点到其他顶点都有路径，那么我们只需要调用一次函数即可

对于强连通图，我们从任何一个顶点出发都只需要调用一次 BFS/DFSBFS/DFSBFS/DFS