题目描述

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点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;
#define Maxlen 30
class Map
{
public:
    bool visit[Maxlen];
    int m[Maxlen][Maxlen];
    int n;
    Map()
    {
        n=0;
    }
    void setmartix(int num,int mx[Maxlen][Maxlen])
    {
        n=num;
        for(int i=0;i<Maxlen;i++)
        {
            for(int j=0;j<Maxlen;j++)
            {
                m[i][j]=0;
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                m[i][j]=mx[i][j];
            }
        }
    }
    void DFSmove()
    {
        for(int i=0;i<Maxlen;i++)
        {
            visit[i]=false;
        }
        for(int i=0;i<n;i++)
        {
            if(visit[i]==false)
                DFS(i);
        }
    }
    void DFS(int v)
    {
        cout<<v<<" ";
        visit[v]=true;
        int *temp=new int[n];///找到与v相连的结点
        for(int i=0;i<n;i++)
            temp[i]=-1;
        int k=0;
        for(int i=0;i<n;i++)
        {
            if(m[v][i]==1)
            {
                temp[k]=i;
                k++;
            }
        }
        int w;
        int i=0;
        for(w=temp[i];w>=0;i++,w=temp[i])
        {
            if(visit[w]==false)
                DFS(w);
        }
        delete []temp;
    }
};
 
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 M;
        M.setmartix(n,a);
        M.DFSmove();
        cout<<endl;
    }
    return 0;
}