深度优先遍历-邻接矩阵实现

输入

输入的第一行包含一个正整数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

提示

在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。另外，算法中描述的FirstAdjVex函数和NextAdjVex函数，需要认真的自行探索并完成。

通过这道题目，应该能够对图的深度优先搜索建立更加直观和清晰的概念。

AC_code

C++

#include <bits/stdc++.h>
using namespace std;
const int N=51;
int a[N][N],vis[N],n;

void dfs(int i)
{
    cout<<i<<" ";
    vis[i]=1;
    for(int j=0;j<n;j++)
    {
        if(!vis[j]&&a[i][j]==1)
            dfs(j);
    }
}

main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            cin>>a[i][j];
    }
    dfs(0);
    cout<<endl;
}