4011基于邻接表的深度优先遍历

描述

一个连通图采用邻接表作为存储结构。设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

输入

多组数据，每组m+2数据行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k，代表边依附的两个顶点。第m+2行有一个整数d，代表从d开始遍历。当n和m都等于0时，输入结束。

输出

每组数据输出一行，为深度优先搜索的遍历结果。每两个数字之间用空格隔开。

输入样例 1

3 2
1 2
1 3
1
2 1
1 2
2
0 0

输出样例 1

1 2 3
2 1

//基于邻接表的深度优先遍历 
#include <iostream>
#define MVNum 100
using namespace std;
typedef struct ArcNode{//边信息 
	int p;//顶点 
	ArcNode *nextarc; //下一条边 
}ArcNode,*ArcList;
typedef struct VNode{//顶点信息
	int name;//存储顶点的代号 
	ArcNode *ArcList;//指向第一条依附于他的边 
}VNode,AdjList[MVNum];//如果此处用链表不好随时调用某顶点的信息
typedef struct{
	AdjList vertices;//图的本体 
	int vexnum,arcnum;//图的当前顶点数和边数 
}ALGraph;
void Create_V(ALGraph &G,int name){//构造顶点 输入逻辑地址
	int pos=++G.vexnum; 
	G.vertices[pos-1].name=name;//vexnum是逻辑地址，所以-1 
	G.vertices[pos-1].ArcList=NULL;
}
void Create_Arc(ALGraph &G,int h,int k){//构造边（由于此次题目图的顺序序号和内容一一对应，此处可以省略查找逻辑地址的过程） 
	int posh=0,posk=0;
	for(int i=1;i<=G.vexnum;i++){//查找左右顶点的逻辑地址 
		if(h==G.vertices[i-1].name) posh=i;
		if(k==G.vertices[i-1].name) posk=i;
	}
	if(posh*posk==0) return;//此处删去也行 题目没做要求 如果边的点不在图中 退出 
	ArcNode *ph=new ArcNode;//h的新邻接点 
	ArcNode *pk=new ArcNode;//p的新邻接点 
	ph->p=k;//p新邻接点的名字
	ph->nextarc=G.vertices[posh-1].ArcList;//前插法 
	G.vertices[posh-1].ArcList=ph;
	pk->p=h;//h新邻接点的名字
	pk->nextarc=G.vertices[posk-1].ArcList;//前插法 
	G.vertices[posk-1].ArcList=pk;
	G.arcnum++;
}
void DFS_G(ALGraph &G){//对邻接表进行深度优先遍历（由于此次题目图的顺序序号和内容一一对应，此处省略查找逻辑地址的过程） 
	int v,top=0;//v代表深度优先遍历的起点，top表示栈顶的位置 
	int been[MVNum],Stack[MVNum];//been数组表示到达过的位置，Stack表示栈 
	for(int i=1;i<=MVNum;i++)//清空been数组 
		been[i-1]=0;
	cin>>v;//输入起点 
	cout<<v;//输出起点
	Stack[top]=v;//栈顶为起点 
	top++;
	been[v-1]=1;//起点到达标记 
	while(top>0){//当栈不为空一直执行 
		int t=0;//用于标记是否能查找到邻接边 
		ArcList p=G.vertices[Stack[top-1]-1].ArcList;//标记p指向栈顶元素的邻接边链表 
		while(p){//当p存在一直找（找到最远的邻接边，由于构造采用前插法，那条边反而是最先构造的，所以优先遍历它） 
			if(!been[p->p-1])
				t=p->p;
			p=p->nextarc;
		}
		if(t==0)//如果t为0，说明没有找到邻接点，出栈 
			top--;
		else{
			cout<<" "<<t;//找到邻接的点了，输出这个点 
			Stack[top]=t;//邻接点入栈 
			top++; 
			been[t-1]=1;//标记这个点来过了 
		}
	}
	cout<<endl;
}
void Calculate(int m,int n){
	ALGraph G;
	G.vexnum=G.arcnum=0;
	for(int i=1;i<=m;i++) Create_V(G,i);//构造前n个顶点 
	for(int i=1;i<=n;i++){//构造n条边 
		int h,k;
		cin>>h>>k;//输入左右顶点 
		Create_Arc(G,h,k);//构造边 
	}
	DFS_G(G); 
}
int main(){
	int m,n;
	while(cin>>m>>n&&m!=0&&n!=0){//每次处理一组数据 
		Calculate(m,n);
	}
	return 0;
}