南昌网站建设咨询南京网站推广排名

题目描述
以邻接矩阵给出一张以整数编号为顶点的图，其中0表示不相连，1表示相连。按深度和广度优先进行遍历，输出全部结果。要求，遍历时优先较小的顶点。如，若顶点0与顶点2，顶点3，顶点4相连，则优先遍历顶点2.

输入
顶点个数
邻接矩阵

输出
DFS
深度遍历输出
WFS
广度遍历输出,

样例输入
3
0 1 1
1 0 1
1 1 0

样例输出
DFS
0 1 2
1 0 2
2 0 1
WFS
0 1 2
1 0 2
2 0 1
 

#include <iostream>
#include <queue>using namespace std;
int* visit;
int num;
int** edge;void DFS(int n) {visit[n] = 1;cout << n << " ";for (int i = 0; i <num; i++) {//判断领顶点if (edge[n][i] == 1 && visit[i] == 0)DFS(i);}
}void BFS(int n) {int temp = n;queue<int>q;q.push(temp);while (!q.empty()) {int t = q.front();q.pop();if (visit[t] == 0) {//没访问过就输出cout << t << " ";visit[t] = 1;}for (int i = 0; i <num; i++) {//把他的领顶点放到队中if (edge[t][i] == 1 && visit[i] == 0) {q.push(i);}}}
}void Reset() {for (int i = 0; i < num; i++)visit[i] = 0;cout << endl;
}int main() {cin >> num;//判断是否走过visit = new int[num];for (int i = 0; i < num; i++)visit[i] = 0;//邻接矩阵edge = new int* [num];for (int i = 0; i < num; i++)edge[i] = new int[num];for (int i = 0; i < num; i++)for (int j = 0; j < num; j++)cin >> edge[i][j];cout << "DFS" << endl;;for (int i = 0; i < num; ++i) {DFS(i);Reset();}cout << "WFS" << endl;;for (int i = 0; i < num; ++i) {BFS(i);Reset();}}