无向图的邻接矩阵的深度优先搜索和广度优先搜索（C++实现）

一、深度优先搜索

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

1. 题目大意

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。
输入
输入的第一行包含一个正整数n，表示图*有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。
输出
只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0
样例输出
0 1 3 2
提示
在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。
通过这道题目，应该能够对图的深度优先搜索建立更加直观和清晰的概念。

2. 代码实现

#include <bits/stdc++.h>
 
int a[50][50],vis[50];
int n;
void dfs(int u);
 
using namespace std;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    dfs(0);
}
 
void dfs(int u) {
    cout << u << " ";
    vis[u] = 1;
    for(int i = 0; i < n; i++){
        if(a[u][i] && !vis[i]){
            dfs(i);
        }
    }
}

二、广度优先搜索

广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点。重复上述过程，直至图中所有顶点都被访问到为止。

1. 题目大意：

读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。
输入
输入的第一行包含一个正整数n，表示图*有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。
输出
只有一行，包含n个整数，表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
4
0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0
样例输出
0 3 1 2
提示
在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。在本题中需要使用队列结构，需要对队列的概念进行复习。

2. 代码实现

#include <bits/stdc++.h>

int a[50][50],vis[50];
int n;
using namespace std;
int main(){
//    ifstream cin("input.txt");
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    queue<int>q;
    q.push(0);
    vis[0]=1;
    while(q.size()>0){
        int u = q.front();
        q.pop();
        cout << u << " ";
        for(int i = 0; i < n; i++){
            if(a[u][i]&&!vis[i]){
                q.push(i);
                vis[i] = 1;
//                cerr<<"size:"<<q.size()<<endl;
            }
        }
    }
}