数据结构实验之图论四：迷宫探索

叁歲伎倆 2022-08-17 14:18 161阅读 0赞

## 数据结构实验之图论四：迷宫探索 ##

####  ####

#### Time Limit: 1000MS Memory limit: 65536K ####

## 题目描述 ##

有一个地下迷宫，它的通道都是直的，而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关；请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

## 输入 ##

连续T组数据输入，每组数据第一行给出三个正整数，分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S，随后M行对应M条边，每行给出一对正整数，表示一条边相关联的两个顶点的编号。

## 输出 ##

若可以点亮所有结点的灯，则输出从S开始并以S结束的序列，序列中相邻的顶点一定有边，否则只输出部分点亮的灯的结点序列，最后输出0，表示此迷宫不是连通图。  
访问顶点时约定以编号小的结点优先的次序访问，点亮所有可以点亮的灯后，以原路返回的方式回到起点。

## 示例输入 ##

1
    6 8 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 4
    3 6
    1 5

## 示例输出 ##

1 2 3 4 5 6 5 4 3 2 1

## 提示 ##

## 来源 ##

xam

## 示例程序 ##

解法一：（邻接表）

#include<stdio.h>
    #include<string.h>
    #include<vector>
    #include <algorithm>
    using namespace std;
    vector<int>V[1010];
    int visited[10100],p[10010],l,sum;
    int cmp(int x,int y)
    {
        return x<y;
    }
    void DFS(int x)
    {
         p[l++]=x;
         visited[x]=1;
        int len=V[x].size(),i;
        if(len>1)
            sort(V[x].begin(),V[x].end(),cmp);
        for(i=0;i<len;i++)
        {
            int h= V[x][i] ;
            if(!visited[h])
            {
                DFS(h);
                p[l++]=x;
            }
        }
    }
    int main()
    {
        int i,j,n,m,k,t,l1,l2;
        scanf("%d",&t);
        while(t--)
        {
            l=0;
            sum=0;
            scanf("%d %d %d",&n,&m,&k);
            for(i=1;i<=n;i++)
                V[i].clear();
            memset(visited,0,sizeof(visited));
            for(i=0;i<m;i++)
            {
                scanf("%d %d",&l1,&l2);
                V[l1].push_back(l2);
                V[l2].push_back(l1);
            }
            DFS(k);
            for(i=0;i<l;i++)
                if(i==0)
                printf("%d",p[i]);
            else
                printf(" %d",p[i]);
            if(l!=2*n-1)
                printf(" 0");
            printf("\n");
        }
    }

解法二：（邻接矩阵）

#include<stdio.h>
    #include<string.h>
    int map[1010][1010],pum[10000],l,visited[10000],sum,n,s;
    void DFS(int x)
    {
        int i;
        visited[x]=1;
        pum[sum++]=x;
        s++;
        for(i=1;i<=n;i++)
            if(visited[i]==0&&map[x][i])
            {
                DFS(i);
                pum[sum++]=x;
            }
    }
    int main()
    {
      int i,j,m,k,t,l1,l2;
      scanf("%d",&t);
      while(t--)
      {
          scanf("%d %d %d",&n,&m,&k);
          sum=0;
          s=0;
          memset(map,0,sizeof(map));
          memset(visited,0,sizeof(visited));
          for(i=0;i<m;i++)
          {
              scanf("%d %d",&l1,&l2);
              map[l1][l2]=1;
              map[l2][l1]=1;
          }
            DFS(k);
          for(i=0;i<sum;i++)
            if(i==0)
            printf("%d",pum[i]);
          else
            printf(" %d",pum[i]);
            if(s!=n)
            printf(" 0");
          printf("\n");
      }
    }