实验6: 地下迷宫探索(注:要求使用邻接表)
1.实验目的
(1)熟练掌握图的存储结构。
(2)熟练掌握图的深度优先遍历方法。
2.实验内容
在现在来说,探索地下通道是一种娱乐益智的游戏。本实验案例以探索地下通道迷宫作为内容。
假设有一个地下通道迷宫,它的通道都是直的,而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关,如图1所示。请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点?
3.实验要求
(1)输入说明:输入第1行给出三个正整数,分别表示地下迷宫的结点数N(1≤ N≤1000,表示通道所有交叉点和端点)、边数M(M≤3000,表示通道数)和探索起始结点编号S(结点从1到N编号)。随后的M行对应M条边(通道),每行给出一对正整数,分别是该条边连通的两个结点的编号。
(2)输出说明:若可以点亮所有结点的灯,则输出从S开始并以S结束的包含所有结点的序列,序列中相邻的节点一定有边(通道);否则虽然不能点亮所有结点的灯,但还是输出点亮部分灯的结点序列,最后输出0,此时表示迷宫不是连通图。
由于深度优先遍历的结点序列是不唯一的,为了使输出具有唯一的结果,约定以编号小的结点优先的次序访问(点灯)。在点亮所有可以点亮的灯后,以原路返回的方式回到起点。
(3)测试用例:
这是我的实验代码,求大神帮忙看一下错在哪里,每次输入到第三行就没法输新的数字了
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
//本题使用的是邻接表储存迷宫图
int* visit[1000];//标记是否访问
typedef struct ANode{
int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct Vnode{
int data; //顶点信息
ArcNode *firstarc; //指向第一条边
}VNode;
typedef struct {
VNode adjlist[1000]; //邻接表
}AdjGraph;
typedef struct{
int data[1000];
int top; //栈顶指针
}path;//设置一个堆栈存放迷宫路径
void InitStack(path *&s){
s=(path *)malloc(sizeof(path));
s->top=-1;
} //初始化堆栈
bool push(path *&s,int e){
if (s->top==1000) //栈满的情况,即栈上溢出
return false;
s->top++; //栈顶指针增1
s->data[s->top]=e; //元素e放在栈顶指针处
return true;
}//进栈
void CreateALGraph(AdjGraph *&G,int adjlist[1000],int num,int edge){ //创建迷宫图
ArcNode *p;
G=(AdjGraph *)malloc(sizeof(AdjGraph));
p=(ArcNode *)malloc(sizeof(ArcNode));
p=G->adjlist[0].firstarc;
int i,n,m,k;
for(i=0;i<num;i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc=NULL;
for(n=0;n<edge;n++){
scanf("%d %d",&k,&m);
p=G->adjlist[k-1].firstarc;
while(p->nextarc!=NULL){
p=p->nextarc;
}
p->adjvex=m;
p->nextarc=NULL;
}
}
void DFS_non_recursive(AdjGraph *&G,path *&s,int begin,int visit[1000]){//借助堆栈求出路径并输出
bool push(path *&s,int e);
int min(int a,int b);
ArcNode *p,*a;
p=(ArcNode *)malloc(sizeof(ArcNode));
a=(ArcNode *)malloc(sizeof(ArcNode));
push(s,begin);
printf("%d",begin);
p=G->adjlist[begin-1].firstarc;
p=p->nextarc;
visit[begin-1]=1;
while(p!=NULL||(G->adjlist[p->adjvex-1].firstarc)->nextarc!=NULL){
a=G->adjlist[p->adjvex-1].firstarc;
push(s,min((p->nextarc)->adjvex,(a->nextarc)->adjvex));
printf("%d ",min((p->nextarc)->adjvex,(a->nextarc)->adjvex));
visit[min((p->nextarc)->adjvex,(a->nextarc)->adjvex)-1]=1;
}
while(s->top=!-1){
s->top--;
printf("%d ",s->data[s->top]);
}
}
void check(int visit[1000],int num){//检查是否连通
int i=0;
while(visit[i]!=0&&i<num){
if(visit[i]=0)
printf("0");
}
}
int min(int a,int b){
if(a>b) return b;
else if(a<b) return a;
else if(a==b) printf("ERROR");
}
int main(){
void InitStack(path *&s);
bool push(path *&s,int e);
void CreateALGraph(AdjGraph *&G,int adjlist[1000],int num,int edge);
void DFS_non_recursive(AdjGraph *&G,path *&s,int begin,int visit[1000]);
void check(int visit[1000],int num);
int min(int a,int b);
int num,edge,begin;
path *s;
AdjGraph *G;
int* adjlist[1000];
scanf("%d %d %d",&num,&edge,&begin);
InitStack(s);
CreateALGraph(G,adjlist[1000],num,edge);
DFS_non_recursive(G,s,begin,visit[1000]);
check(visit[1000],num);
return 0;
}