DS图遍历–深度优先搜索
题目描述
给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始
注意：图n个顶点编号从0到n-1
代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开
样例输入
2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0
样例输出
0 2 1 3
0 3 2 1 4
#include<iostream> #include<string> using namespace std; const int MaxLen = 20; class Map { private: bool vist[MaxLen]; int matrix[MaxLen][MaxLen]; int vexnum; void DFS(int v); public: void setmatrix(int vnum, int mx[MaxLen][MaxLen]); void DFSTraverse(); }; void Map::setmatrix(int vnum, int mx[MaxLen][MaxLen]){ int i, j; vexnum = vnum; for (i = 0; i < MaxLen; i++) for (j = 0; j < MaxLen; j++) matrix[i][j] = 0; for (i = 0; i < vexnum; i++) for (j = 0; j < vexnum; j++) matrix[i][j] = mx[i][j]; } void Map::DFSTraverse(){ for (int i = 0; i < MaxLen; i++) vist[i] = false; for (int i = 0; i < vexnum; i++) if (!vist[i]) DFS(i); } void Map::DFS(int v){ int w, i, k; cout << v << " "; vist[v] = true; int *adjvex = new int[vexnum]; for (i = 0; i < vexnum; i++) adjvex[i] = -1; k = 0; for (i = 0; i < vexnum; i++) if (matrix[v][i] == 1) adjvex[k++] = i; i = 0; for (w=adjvex[i]; w >=0;w=adjvex[++i]) { if (!vist[w]) DFS(w); } delete[]adjvex; } int main(){ int t; cin >> t; while (t--){ int n; cin >> n; int a[MaxLen][MaxLen]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j]; Map map; map.setmatrix(n, a); map.DFSTraverse(); cout << endl; } }
转载于:https://www.cnblogs.com/Liu269393/p/10222700.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101221.html原文链接：https://javaforall.net
