当前位置：首页 > news >正文

图的遍历|深度优先搜索|广度优先搜索(C)

news 来源：原创 2025/6/19 5:58:30

图的基本操作

图的基本操作是独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。
图的基本操作主要包括（仅抽象地考虑，所以忽略各变量的类型）：

Adjacent(G, x, y);       // 判断图G是否存在边<x,y>或(x,y)
Neighbors(G, x);         // 列出图G中与节点x邻接的边
InsertVertex(G, x);      // 在图G中插入顶点x
DeleteVertex(G, x);      // 在图G中删除顶点x
AddEdge(G, x, y);        // 若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边
RemoveEdge(G, x, y);     // 若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边
FirstNeighbor(G, x);     // 求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1
NextNeighbor(G, x, y);   // 假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
Get_edge_value(G, x, y);    // 获取图G中边(x,y)或<x,y>对应的权值
Set_edge_value(G, x, y, v); // 设置图G中边(x,y)或<x,y>对应的权值为v

图的遍历

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

广度优先搜索

广度优先搜索（Breadth-First-Search,BFS）类似于二叉树的层序遍历算法。
基本思想是：

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

伪代码

bool visited[maxVertexNum];         // 访问标记数组
void BFSTraverse(Graph G)           // 对图G进行广度优先遍历
{for(i = 0; i < G.vexnum; ++i){// 访问标记数组初始化visited[i] = false;}// 初始化辅助队列QInitQueue(Q);// 从0号顶点开始遍历for(i = 0; i < G.vexnum; ++i){// 对每个连通分量调用一次BFS()if (!visited[i])// 若vi未访问过，从vi开始调用BFS()BFS(G, i);}
}

    0 —— 1|    |2    3

顶点：0, 1, 2, 3
边：(0, 1), (0, 2), (1, 3)

初始化：
visited[] = {false, false, false, false}。
队列初始化为空。
开始遍历：
从顶点 0 开始，因为 visited[0] == false。
将 0 入队，访问 0。
BFS 遍历：
访问 0 的邻接顶点 1 和 2，并将它们入队：
```
visited[] = {true, true, true, false}
Queue: [1, 2]
```
出队顶点 1，访问 1 的邻接顶点 3，并将 3 入队：
```
visited[] = {true, true, true, true} 
Queue: [2, 3]
```
出队顶点 2，发现它没有未访问的邻接顶点。
出队顶点 3，发现它没有未访问的邻接顶点。
完成第一个连通分量：
此时队列为空，连通分量遍历完成。
继续检查其他顶点：
visited[] = {true, true, true, true}，所有顶点已访问，无需再调用 BFS()。

邻接表广度优先搜索

void BFS(ALGrapg G, int i)
{// 访问初始顶点ivisit(i);// 对i做已访问标记visited[i] = true;// 顶点i入队EnQueue(Q, i);while (!QueEmpty(Q)){// 队首顶点v出队DeQueue(Q, v);// 检测v的所有邻接点for (p = G.vertices[v].firstarc; p; p = p->nextarc){w = p->adjvex;if (visited[w] == false){// w为v的尚未访问的邻接点，访问wvisit(w);// 对w做已访问标记visited[w] = true;// 顶点w入队EnQueue(Q, w);}}}
}

初始操作：
访问起始顶点 i。
标记 i 为已访问，并将其入队。
进入队列循环：
当队列不空时，执行以下操作：
1. 队首顶点 v 出队。
2. 遍历 v 的所有邻接点。
对于每个邻接点 w：
如果 w 未被访问，则执行：
1. 访问 w
2. 标记 w 为已访问
3. 将 w 入队。
终止条件：
当队列为空时，广度优先搜索结束。

邻接矩阵广度优先搜索

void BFS(MGraph G, int i)
{// 访问初始节点ivisit(i);// 对i做已访问标记visited[i] = true;// 顶点i入队EnQueue(Q, i);while (!QueEmpty(Q)){// 队首顶点v出队DeQueue(Q, v);// 检测v的所有邻接点for (w = 0; w < G.vexnum; w++){if (visited[w] == false && G.edge[v][w] == 1){// w为v的尚未访问的邻接点，访问wvisit(w);// 对w做已访问的标记visited[w] = true;// 顶点w入队EnQueue(Q, w);}}}
}

辅助数组visited[]标志顶点是否被访问过，其初始状态为FALSE。在图的遍历过程中，一旦某个顶点v被访问，就立即置visited[i]为TRUE，防止它被多次访问。

深度优先搜索

与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的先序遍历。
如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”地搜索一个图。
它的基本思想如下：

首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任意一个顶点 $w_{1}$ ，再访问与w邻接且未被访问的任意一个顶点 $w_{2}$ …
重复上述过程。
当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

bool visited[maxVertexNum];        // 访问标记数组
void DFSTraverse(Graph G)          // 对图G进行深度优先遍历
{for (i = 0; i < G.vexnum; i++) // 初始化已访问标记数组visited[i] = false;         for (i = 0; i < G.vexnum; i++) // 从v0开始遍历// 对尚未访问过的顶点调用DFS()if (!visited[i])DFS(G, i);
}

初始化访问标记数组：
遍历所有顶点，将 visited[] 数组初始化为 false，表示所有顶点都尚未访问。
开始遍历：
遍历所有顶点，对于每个未被访问的顶点i，调用 DFS(G, i) 进行深度优先搜索。

邻接表深度优先搜索

void DFS(ALGraph G, int i)
{// 访问初始顶点ivisit(i);// 对i做已访问标记visited[i] = true;// 检查i的所有邻接点for (p = G.vertices[i].firstarc; p; p->nextarc){// 获取邻接点 jj = p->adjvex;// 如果邻接点 j 未被访问if (visited[j] == false)// j为i的尚未访问的邻接点，递归访问jDFS(G, j);}
}

访问当前顶点 i：调用 visit(i) 进行访问操作，例如打印顶点编号。
标记已访问：visited[i] = true，确保不会重复访问当前顶点。
遍历所有邻接点：
使用 for 循环遍历顶点i的邻接点列表，依次访问所有邻接点。
对每个尚未访问的邻接点j，递归调用 DFS(G, j)，继续深度搜索。
递归结束条件：当邻接点全部遍历完毕，返回上一层调用。

0 - 1
|   |
2   3顶点  邻接表0    → 1 → 21    → 0 → 32    → 03    → 1

初始状态

visited[] = {false, false, false, false}。

DFS(G, 0)：

访问顶点 0：visit(0) → 标记 visited[0] = true。
遍历邻接点：
- j=1：visited[1] = false，递归调用 DFS(G, 1)。

DFS(G, 1)：

访问顶点 1：visit(1) → 标记 visited[1] = true。
遍历邻接点：
- j=0：visited[0] = true，跳过。
- j=3：visited[3] = false，递归调用 DFS(G, 3)。

DFS(G, 3)：

访问顶点 3：visit(3) → 标记 visited[3] = true。
遍历邻接点：
- j=1：visited[1] = true，跳过。
  回溯到 DFS(G, 0)，继续遍历 0 的邻接点：

j=2：visited[2] = false，递归调用 DFS(G, 2)。

DFS(G, 2)：

访问顶点 2：visit(2) → 标记 visited[2] = true。
遍历邻接点：
- j=0：visited[0] = true，跳过。

0 → 1 → 3 → 2

邻接矩阵深度优先搜索

void DFS(MGraph G, int i)
{// 访问初始顶点ivisit(i);// 对i做已访问标记visited[i] = true;// 检测i的所有邻接点for (j = 0; j < G.vexnum; j++){if (visited[j] == false && G.edge[i][j] == 1)// j为i尚未访问过的邻接点，递归访问jDFS(G, j);}
}

访问当前顶点 i：
- visit(i) 对顶点 i 执行访问操作，例如输出顶点编号。
- 标记 visited[i] = true，防止重复访问。
检测所有邻接点：
- 使用 for 循环遍历顶点j（0 到 G.vexnum-1）。
- 如果 G.edge[i][j] == 1（表示 i 和 j 有一条边）且 j 未访问：
  - 递归调用 DFS(G, j)，继续访问顶点 j。
递归结束条件：
- 遍历完 i 的所有邻接点后，返回上一层递归调用。

初始状态

visited[] = {false, false, false, false}。
从顶点 0 开始调用 DFS(G, 0)。

步骤 1：`DFS(G, 0)`

访问 0，visited[0] = true。
遍历邻接点：
- j=1：G.edge[0][1] == 1 且 visited[1] == false。
  - 递归调用 DFS(G, 1)。

步骤 2：`DFS(G, 1)`

访问 1，visited[1] = true。
遍历邻接点：
- j=0：visited[0] == true，跳过。
- j=3：G.edge[1][3] == 1 且 visited[3] == false。
  - 递归调用 DFS(G, 3)。

步骤 3：`DFS(G, 3)`

访问 3，visited[3] = true。
遍历邻接点：
- j=1：visited[1] == true，跳过。
返回 DFS(G, 1)。
回到 DFS(G, 0)：
j=2：G.edge[0][2] == 1 且 visited[2] == false。
- 递归调用 DFS(G, 2)。

步骤 4：`DFS(G, 2)`

访问 2，visited[2] = true。
遍历邻接点：
- j=0：visited[0] == true，跳过。
返回 DFS(G, 0)。

图的基本操作

图的遍历

广度优先搜索

伪代码

邻接表广度优先搜索

邻接矩阵广度优先搜索

深度优先搜索

邻接表深度优先搜索

初始状态

DFS(G, 0)：

DFS(G, 1)：

DFS(G, 3)：

DFS(G, 2)：

邻接矩阵深度优先搜索

初始状态

步骤 1：DFS(G, 0)

步骤 2：DFS(G, 1)

步骤 3：DFS(G, 3)

步骤 4：DFS(G, 2)

相关文章：

步骤 1：`DFS(G, 0)`

步骤 2：`DFS(G, 1)`

步骤 3：`DFS(G, 3)`

步骤 4：`DFS(G, 2)`