算法笔记:图的遍历
2021/8/14 20:06:13
本文主要是介绍算法笔记:图的遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)。
- 深度优先遍历(Depth_First_Search)
从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。这是连通图的情况,如果是非连通图,只需要对它的连通分量分别进行深度优先遍历,即在先前一个顶点进行一次深度优先遍历后,若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
如果我们用的是邻接矩阵的方式,则代码如下:
1 typedef bool Boolean; // Boolean是布尔类型,其值是TRUE或FALSE 2 Boolean visited[MAX]; // 访问标志的数组 3 // 邻接矩阵的深度优先递归算法 4 void DFS(MGraph G, int i) { 5 visited[i] = TRUE; 6 printf("%c ", G.vexs[i]); // 打印顶点,也可以其他操作 7 for (int j = 1; j < G.numVertexes; j++) 8 if (G.arc[i][j] == 1 && !visited[j]) 9 DFS(G, j); // 对未访问的邻接顶点递归调用 10 } 11 // 邻接矩阵的深度遍历操作 12 void DFSTraverse(MGraph G) { 13 for (int i = 0; i < G.numVertexes; i++) 14 visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态 15 for (int i = 0; i < G.numVertexes; i++) 16 if (!visited[i]) // 对未访问过的顶点调用DFS,若是连通图,只会执行一次 17 DFS(G, i); 18 }
如果图结构是邻接表结构,其DFSTraverse函数的代码是几乎相同的,只是在递归函数中因为将数组换成了链表而有所不同。代码如下:
1 // 邻接表的深度优先递归算法 2 void DFS(GraphAdjList GL, int i) { 3 EdgeNode *p; 4 visited[i] = TRUE; 5 printf("%c ", GL->adjList[i].data); // 打印顶点,也可以其他操作 6 p = GL->adjList[i].firstedge; 7 while (p) { 8 if (!visited[p->adjvex]) 9 DFS(GL, p->adjvex); 10 p = p->next; 11 } 12 } 13 // 邻接表的深度遍历操作 14 void DFSTraverse(GraphAdjList GL) { 15 for (int i = 1; i < GL->numVertexes; i++) 16 visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态 17 for (int i = 1; i < GL->numVertexes; i++) 18 if (!visited[i]) // 对未访问过的顶点调用DFS 19 DFS(GL, i); 20 }
- 广度优先遍历(Breadth_First_Search)
邻接矩阵结构的广度优先遍历算法代码如下:
1 void BFSTraverse(MGraph G) { 2 Queue Q; 3 for (int i = 0; i < G.numVertexes; i++) 4 visited[i] = FALSE; 5 InitQueue(&Q); // 初始化一辅助用的队列 6 for (int i = 0; i < G.numVertexes; i++) { // 对每一个顶点loop 7 if (!visited[i]) { // 若是未访问过就处理 8 visited[i] = TRUE; // 设置当前顶点访问过 9 printf("%c ", G.vexs[i]); // 打印顶点,也可以其他操作 10 EnQueue(&Q, i); // 将此顶点入队 11 while (!QueueEmpty(Q)) { // 若当前队列不为空 12 DeQueue(&Q, &i); // 将队中元素出队,赋值给i 13 for (int j = 0; j < G.numVertexes; j++) { 14 // 判断其他顶点若与当前顶点存在边且未访问过 15 if (G.arc[i][j] == 1 && !visited[j]) { 16 visited[j] = TRUE; // 将找到的此顶点标记为已访问 17 printf("%c ", G.vexs[j]); // 打印顶点 18 EnQueue(&Q, j); // 将找到的此顶点入队 19 } 20 } 21 } 22 } 23 } 24 }
邻接表的广度优先遍历的代码的邻接矩阵差距不大。代码如下:
1 void BFSTraverse(GraphAdjList GL) { 2 EdgeNode *p; 3 Queue Q; 4 for (int i = 0; i < GL->numVertexes; i++) 5 visited[i] = FALSE; 6 InitQueue(&Q); 7 for (int i = 0; i < GL->numVertexes; i++) { 8 if (!visited[i]) { 9 visited[i] = TRUE; 10 printf("%c ", GL->adjList[i].data); // 打印顶点,也可以其他操作 11 EnQueue(&Q, i); 12 while (!QueueEmpty(Q)) { 13 DeQueue(&Q, &i); 14 p = GL->adjList[i].firstedge; // 找到当前顶点边表链表头指针 15 while (p) { 16 if (!visited[p->adjvex]) { // 若此顶点未被访问 17 visited[p->adjvex] = TRUE; 18 printf("%c ", GL->adjList[p->adjvex].data); 19 Enqueue(&Q, p->adjvex); // 将此顶点入队 20 } 21 p = p->next; // 指针指向下一个邻接点 22 } 23 } 24 } 25 } 26 }
这篇关于算法笔记:图的遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求