BJFU_資料結構習題_282基于鄰接表的深度優先周遊

歡迎登入北京林業大學OJ系統

http://www.bjfuacm.com

282基于鄰接表的深度優先周遊

描述

一個連通圖采用鄰接表作為存儲結構。設計一個算法，實作從頂點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>
using namespace std;
#define OK 0
#define ERROR -1
#define MAX 100
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
typedef struct
{
	int vexnum;
 	int arcnum;
	LinkList V[MAX];
}ALGragh;
int CreateUDN(ALGragh &G,int vexnum,int arcnum)
{
	G.vexnum=vexnum;
	G.arcnum=arcnum;
	if(G.vexnum>MAX)
    	return ERROR;
  	for(int i=1;i<=vexnum;i++)
	{
		G.V[i]=new LNode;
		G.V[i]->data=i;
		G.V[i]->next=NULL;
	}
  	while(arcnum--)
	{
      	int x,y;
		cin>>x>>y;
      	LinkList p=new LNode;
		p->data=y;
		p->next=G.V[x]->next;	
      	G.V[x]->next=p;	
        LinkList q=new LNode;
		q->data=x;
		q->next=G.V[y]->next;
		G.V[y]->next=q;
	}
  	return OK;
}
int DFS_AL(ALGragh G)
{
	int d,top=0,visit[MAX],Stack[MAX];
	for(int i=0;i<MAX;i++)
		visit[i]=0;
	cin>>d;
	cout<<d;
	Stack[top++]=d;
	visit[d]=1;
	while(top>0)
	{
		int t=-1;
		LinkList p=G.V[Stack[top-1]];	
		while(p)
		{
			if(!visit[p->data])
				t=p->data;
			p=p->next;
		}
		if(t==-1)
			top--;
		else
		{
			cout<<" "<<t;
			Stack[top++]=t;
			visit[t]=1;
		}
	}
	cout<<endl;
	return OK;
}
int main()
{
	int n,m;
	while(cin>>n>>m&&n!=0&&m!=0)
	{
		ALGragh G;
       	CreateUDN(G,n,m);
   		DFS_AL(G);
	}
	return 0;
}