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

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

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

#include <stdio.h> #include <stdlib.h> #include <string.h> #include<queue> #define INF = 0x3f3f3f3f #define MAX 100 using namespace std; typedef struct arcnode { int adj; } arcnode, adjmatrix[110][110]; typedef struct { adjmatrix a; int vn; int an; } MG; int create(MG &g, int n, int m) { int i, j; int v1, v2; g.vn = n; g.an = m; for(i=1; i<=g.vn; i++) for(j=1; j<=g.vn; j++) g.a[i][j].adj = 0; for(i=1; i<=g.an; i++) { scanf("%d %d", &v1, &v2); g.a[v1][v2].adj = 1; g.a[v2][v1] = g.a[v1][v2]; } return 1; } int v[110]; int b[110]; int c; void dfs(MG &g, int i) { int j; //若不在函数内定义则无法回溯 b[c++] = i; v[i] = 1; for(j=1; j<=g.vn; j++) { if(g.a[i][j].adj==1&&!v[j]) { dfs(g, j); b[c++] = i; //注意等于i（原路返回相当于回溯的过程） } } } int main() { int t; int n, m, k, i, j; MG g; scanf("%d", &t); while(t--) { memset(v, 0, sizeof(v)); memset(b, 0, sizeof(b)); c=0; scanf("%d %d %d", &n, &m, &k); create(g, n, m); dfs(g, k); for(i=0; i<c; i++) { if(i==0) printf("%d", b[i]); else printf(" %d", b[i]); } if((c+1)/2 != n) printf(" 0"); if(t!=0) printf("\n"); } }

#include <stdio.h> #include <stdlib.h> #include <queue> #include <string.h> using namespace std; int a[1010][1010]; int v[1010]; int b[1010]; int n, m; int k; void dfs(int i) { int j; v[i] = 1; b[k++] = i; for(j=1; j<=n; j++) { if(a[i][j]==1&&!v[j]) { dfs(j); b[k++] = i; } } } int main() { int i, j, t, v2, v1, s; scanf("%d", &t); while(t--) { k = 1; memset(v, 0, sizeof(v)); scanf("%d %d %d", &n, &m, &s); for(i=1; i<=n; i++) for(j=1; j<=n; j++) a[i][j] = 0; while(m--) { scanf("%d %d", &v1, &v2); a[v1][v2] = a[v2][v1] = 1; } dfs(s); for(i=1; i<k; i++) { if(i==1) printf("%d", b[i]); else printf(" %d", b[i]); } if(k/2!=n) printf(" 0"); if(t!=0) printf("\n"); } }