#include <iostream.h>
#include <malloc.h>
#define vnum 20     //定義最多的頂節(jié)點(diǎn)  
typedef struct arcnode  //邊結(jié)構(gòu)
{
	int adjvex;      //下一條邊的始點(diǎn)編號(hào)
	struct arcnode *nextarc; //下一條邊指針
}arcnode;
typedef struct vexnode  //定義頂點(diǎn)數(shù)組
{
	int vertex;  //頂點(diǎn)編號(hào)
    arcnode *firstarc; //指向第一條邊的指針
}adjlist[vnum];
typedef struct graphs  //圖類(lèi)型
{
	adjlist adjlist;  //頂點(diǎn)數(shù)組
	int vexnum,arcnum;  //頂點(diǎn)個(gè)數(shù)和邊條數(shù)
}graph;
void create(graph *g)
{
	int n,e,i,j,k;
	arcnode *p;
	cout<<"創(chuàng)建一個(gè)圖: "<<endl;
	cout<<" 頂點(diǎn)數(shù) ";
	cin>>n;
	cout<<"邊數(shù)：";
	cin>>e;
	g->vexnum=n;
	g->arcnum=e;
	for(i=0;i<n;i++)
	{
		g->adjlist[i].vertex=i;
		g->adjlist[i].firstarc=NULL;
	}
	for(k=0;k<e;k++)
	{
        cout<<" 第"<<k+1<< "條邊(節(jié)點(diǎn)號(hào)從0到"<<n-1<<")";
		cin>>i>>j;
		p=(arcnode *)malloc(sizeof (arcnode));//創(chuàng)建邊結(jié)點(diǎn) 
		p->adjvex=j;
		p->nextarc=g->adjlist[i].firstarc;//將p插入到adjlist[i]鏈表的前面
		g->adjlist[i].firstarc=p;	
	}
}
void dfs(graph g,int v,int visited[])
{
	arcnode *p;
	cout<<v<<" ";
	visited[v]=1;
	p=g.adjlist[v].firstarc;
	while (p!=NULL)
	{
		if (!visited[p->adjvex])
			dfs(g,p->adjvex,visited);
		p=p->nextarc;
	}
}
void bfs(graph g,int v)
{
	int quene[vnum],rear=0,first=0;
	int visited[vnum],i;
	arcnode *p;
	for(i=0;i<vnum;i++)
		visited[i]=0;
	cout<<v<<" ";
	visited[v]=1;
	rear++;
	quene[rear]=v;
	while (rear!=first)
	
	{
		first++;
		v=queue[first];
		p=g.adjlist[v].firstarc;
		while (p!=NULL)
		{
			if (!visited[p->adjvex])
			{
				cout<<p->adjvex<<" ";
				visited[p->adjvex]=1;
				rear++;
				queue[rear]=p->adjvex;
			}
			p=p->nextarc;
		}
	}
}
void disp(graph *g)
{
    int i,h;
	arcnode *p;
	cout<<"輸出圖："<<endl;
	for(i=0;i<g->vexnum;i++)
	{ 
		p=g->adjlist[i].firstarc;
		h=0;
  	    while(p!=NULL)
		{
		  cout<<" ("<<i<<","<<p->adjvex<<")";
		  p=p->nextarc;
		  h=1;
		}
 	      if(h==1) cout<<endl;
	}
}
void main()
{
	graph g;
	int visited[vnum] , v;
	for(int i=0;i<vnum;i++)
		visited[i]=0;
	create(&g);
	disp(&g);
	cout<<"輸入頂點(diǎn) ";
	cin>>v;
	cout<<"深度優(yōu)先序列 ";
    dfs( g, v,visited);
	cout<<endl;
	cout<<"廣度優(yōu)先序列 ";
    bfs(g, v);
	cout<<endl;


}