数据结构实验之图论四:迷宫探索
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
有一个地下迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关;请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点?
Input
连续T组数据输入,每组数据第一行给出三个正整数,分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S,随后M行对应M条边,每行给出一对正整数,表示一条边相关联的两个顶点的编号。
Output
若可以点亮所有结点的灯,则输出从S开始并以S结束的序列,序列中相邻的顶点一定有边,否则只输出部分点亮的灯的结点序列,最后输出0,表示此迷宫不是连通图。
访问顶点时约定以编号小的结点优先的次序访问,点亮所有可以点亮的灯后,以原路返回的方式回到起点。
Sample Input
1
6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5
Sample Output
1 2 3 4 5 6 5 4 3 2 1
Hint
Source
xam
会有两种不同的图建立方式,给大家呈现一下
1:正常的用struck定义+DFS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{
int u, v;
int aa[1001][1001];
int visit[1001];
} graph;
graph a;
int que[1001];
int c;
void dfs(int m)
{
a.visit[m] = 1;
que[c++] = m;
for (int i = 1 ; i <= a.v ; i++)
{
if (!a.visit[i] && a.aa[m][i]==1)
{
dfs(i);
que[c++] = m;
}
}
}
int main()
{
int n ;
scanf("%d", &n);
while(n--)
{
memset(a.aa, 0, sizeof (a.aa));
memset(a.visit, 0, sizeof (a.visit));
int s, uu,vv;
scanf("%d%d%d", &a.u, &a.v, &s);
for (int i = 0 ; i < a.v ; i++)
{
scanf("%d %d", &uu,&vv);
a.aa[uu][vv] = a.aa[vv][uu] = 1;
}
c = 0;
dfs(s);
for (int i = 0 ; i < c ; i++)
{
if (!i)
printf("%d", que[i]);
else
printf(" %d", que[i]);
}
if (c == a.u*2-1)
{
printf("\n");
}
else
{
printf(" 0\n");
}
}
return 0;
}
2:
这是一个比较偷懒 的方法,我可以用一个二维数组来储存图的点与边 的关系
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int a[1001][1001];
int visit[1001];
int que[1001];
int c;
void dfs(int m , int k)
{
visit[k] = 1;
que[c++] = k;
for (int i = 1 ; i <= m ; i++)
{
if (a[k][i] == 1 && !visit[i])
{
dfs(m,i);
que[c++] = k;
}
}
}
int main()
{
int i , n , m , u ,v , s , t;
scanf("%d" , &t);
while(t--)
{
memset(a , 0 , sizeof (a));
memset(visit , 0 , sizeof (visit));
scanf("%d%d%d" , &n , &m , &s);
for (i = 0 ; i < m ; i++)
{
scanf("%d %d" , &u , &v);
a[u][v] = a[v][u] = 1;
}
c = 0;
dfs(n , s);
for (i = 0 ; i < c ; i++)
{
if (!i)
{
printf("%d" , que[i]);
}
else
{
printf(" %d" , que[i]);
}
}
if (c == 2 * n - 1)
printf("\n");
else
printf(" 0\n");
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)