数据结构实验之图论四：迷宫探索【dfs 求路径】

分析：起点已知，开个数组来存放路径，注意 vis 数组要初始化！另外，不能忘记了题目还要求回去的路径，只要在 dfs 之后加上就可以了。

#include <bits/stdc++.h>

using namespace std;

int path[1000 * 2 + 10];

int vis[1005];

int gra[1002][1002];

int num = 0;

void dfs(int x, int n)

{

    vis[x] = 1;

    path[num ++] = x;

    for(int i = 1; i <= n; i ++)

    {

        if(!vis[i] && gra[x][i]){

            vis[i] = 1;

            dfs(i,n);

            path[num ++] = x;

        }

    }

    return ;

}

int main()

{

    int t,n,m,s;

    while(~scanf("%d",&t)){

        while(t--)

        {

            scanf("%d%d%d",&n,&m,&s);

            for(int i = 0; i <= n; i ++)

            {

                for(int j = 0; j <= n; j ++ )gra[i][j] = 0;

            }

            int u,v;

            for(int i = 0; i < m; i ++){

                scanf("%d%d",&u,&v);

                gra[u][v] = gra[v][u] = 1;

            }

            num = 0;

            memset(vis,0,sizeof(vis));

            dfs(s,n);

            for(int i = 0; i < num; i ++)

            {

                if(i == 0)printf("%d",path[i]);

                else printf(" %d",path[i]);

            }

            if(num != 2 * n - 1)printf(" 0");

            printf("\n");

        }

    }

    return 0;

}

巴特西

数据结构实验之图论四：迷宫探索【dfs 求路径】

最新文章

热门文章