BJFU_数据结构习题_282基于邻接表的深度优先遍历

布满荆棘的人生 2023-05-29 03:24 22阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][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;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com