无向图的深度优先遍历

无向图的深度优先遍历问题 实现对于无向图的深度优先遍历 和上一篇博客中的实现结点全部遍历且每个结点只经过一次问题不太相同 上一篇博客中的方法 如果一个图中不存在这样的路径 例如七桥问题 则不会输出结果 但是对于本篇博客 针对于一个无向图而言

大家好,我是讯享网,很高兴认识大家。

问题:

实现对于无向图的深度优先遍历,和上一篇博客中的实现结点全部遍历且每个结点只经过一次问题不太相同!上一篇博客中的方法,如果一个图中不存在这样的路径(例如七桥问题)则不会输出结果,但是对于本篇博客,针对于一个无向图而言,不管有没有这样的一次全部遍历的路径,都会存在遍历其全部结点的路径。

1)我们使用无向图的邻接矩阵来存储图模型,并且后续的操作也在这上面完成;

2)其中主要用到回溯的方法,采用递归思想(其设计原理为stack,很适用于这类深度搜索问题);


讯享网

3)和上一篇博文中的方法的异同!:

  • 都是采用回溯的方法
  • 上一篇博文要求找到所有的一次性路径,因此需要对于所有的可能结果进行查找,并在路径生成时对其进行判断
  • 本篇博文只需要找到这么一条深度遍历的路径,直到所有的结点都被访问过为止(有一个问题想问问各位博友们:假设每个结点都有多个可选择后续结点进行访问,那么这个深度优先遍历的路径是不是不唯一的?)
  • 由于上述两点不同,因此在对其完成时的状态进行定义部分不一样(需要注意很小的几个return语句,合适结束递归)

程序:

#include<iostream> #include<algorithm> #include<stack> using namespace std; //深度优先搜索 void display(int *b) { cout << "从1号结点出发: 0 -->"; int next = 0; for (int i = 0; i < 5; i++) { if (b[next] == -1) { cout << " 至此结束!" << endl; } else { cout << b[next] ; next = b[next]; if (b[next] != -1) { cout << " --> "; } } } cout << endl; } int checkVisited(int *visited) { int flag = 1; for (int i = 0; i < 5; i++) { if (visited[i] == 0) { flag = 0; } } return flag; } //深度优先搜索 int dfs(int a[][5], int *b, int n, int *visited) { if (checkVisited(visited)) { display(b); return 1; } if (b[n]!=-1) { return 0; } for (int i = 0; i < 5; i++) { if (a[n][i] != 0 && visited[i]==0) { b[n] = i; visited[i] = 1; int index = dfs(a, b, i, visited); if (!index) { b[n] = -1; visited[i] = 0; } } } } int main() { int a[5][5] = { { 0,1,1,0,1 }, { 1,0,1,0,1 }, { 1,1,0,0,1 }, { 0,0,0,0,1 }, { 0,1,1,1,0 } }; int b[5] = { -1,-1,-1,-1, -1}; int visited[5] = { 1,0,0,0,0 }; dfs(a, b, 0, visited); system("pause"); return 0; }

讯享网

结果:

小讯
上一篇 2025-03-08 16:27
下一篇 2025-01-16 14:02

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78838.html