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; } }