1. 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> using namespace std; const int Maxlen = 20; class Map { private: bool Visit[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 < Maxlen; i++) for (j = 0; j < Maxlen; j++) Matrix[i][j] = mx[i][j]; } void Map::DFSTraverse() { int v; for (int i = 0; i < Maxlen; i++) Visit[i] = false; for (int i = 0; i < Vexnum; i++) { if (!Visit[i]) DFS(i); } cout << endl; } void Map::DFS(int v) { int w, i, k; Visit[v] = true; cout << v << " "; 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]) AdjVex[k++] = i; i = 0; for (i = 0; i < k; i++) { w = AdjVex[i]; if (!Visit[w]) DFS(w); } delete[] AdjVex; } int main() { int t; cin >> t; while (t--) { int n, i, j; cin >> n; int mx[Maxlen][Maxlen]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { cin >> mx[i][j]; } Map m; m.SetMatrix(n, mx); m.DFSTraverse(); } }
2. 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 3 1
0 3 4 2 1
参考代码
#include <iostream> #include <queue> using namespace std; const int Maxlen = 20; class Map { private: bool Visit[Maxlen]; int Matrix[Maxlen][Maxlen]; int Vexnum; void DFS(int v); void BFS(int v); public: void SetMatrix(int vnum, int mx[Maxlen][Maxlen]); void DFSTraverse(); void BFSTraverse(); }; 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 < Maxlen; i++) for (j = 0; j < Maxlen; j++) Matrix[i][j] = mx[i][j]; } void Map::DFSTraverse() { int v; for (int i = 0; i < Maxlen; i++) Visit[i] = false; for (int i = 0; i < Vexnum; i++) { if (!Visit[i]) DFS(i); } cout << endl; } void Map::DFS(int v) { int w, i, k; Visit[v] = true; cout << v << " "; 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]) AdjVex[k++] = i; i = 0; for (i = 0; i < k; i++) { w = AdjVex[i]; if (!Visit[w]) DFS(w); } delete[] AdjVex; } void Map::BFSTraverse() { BFS(0); } void Map::BFS(int v) { int w, u, i, k; int *Adjvex = new int[Vexnum]; queue<int> Q; for (i = 0; i < Vexnum; i++) Visit[i] = false; for (v = 0; v < Vexnum; ++v) { if (!Visit[v]) { cout << v << " "; Visit[v] = true; Q.push(v); while (!Q.empty()) { u = Q.front(); Q.pop(); k = 0; for (i = 0; i < Vexnum; i++) if (Matrix[u][i]) Adjvex[k++] = i; i = 0; for (i = 0; i < k; i++) { w = Adjvex[i]; if(!Visit[w]) { Visit[w] = true; cout << w << " "; Q.push(w); } } } } } cout << endl; } int main() { int t; cin >> t; while (t--) { int n, i, j; cin >> n; int mx[Maxlen][Maxlen]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { cin >> mx[i][j]; } Map m; m.SetMatrix(n, mx); m.BFSTraverse(); } }
