//用鄰接表實現無向圖的深度優先搜索遍歷
#include<iostream.h>
const   int      n =8;            // 表示圖中最大頂點數
const   int      e= 10;           // 圖中最大邊數
typedef int elemtype;
struct  link                       //定義鏈表類型
{ 
   elemtype   data ;
   link  *next ;
};
struct  node                     //定義鄰接表的表頭類型
{  
elemtype   v;            //頂點信息
link   *next;
}a[n+1];
int visited[n];
void  creatlink( )
{  int i,j,k ;
 link   *s ;
for(i=1; i<=n;i++)                   //建立鄰接表頭結點
{ a[i].v=i ;
   a[i].next=NULL;
 }
for(k=1; k<=e;k++)
{ cout<<"請輸入一條邊";
 cin>>i>>j ;                      //輸入一條邊 (i,j)
 cout<<endl;
 s=new  link;                     //申請一個動態存儲單元
s->data=j ;
s->next=a[i].next ;
a[i].next=s ;
s=new  link;               
s->data=i ;
s->next=a[j].next ;
a[j].next=s ;
}
}
void  dfs1(int i)
{ link *p;
   cout<<a[i].v<<"  " ;              //輸出訪問頂點
   visited[i]=1;                //全局數組訪問標記置為1表示已訪問
   p=a[i].next;
   while (p!=NULL)
  {  if  (!visited[p->data])  dfs1(p->data);

p=p->next;
}
}

void main( )
{ link *p;
   creatlink( );
   for(int i=1;i<=n;i++)
   {  p=a[i].next;
      cout<<a[i].v<<"->";
      while(p->next!=NULL)
	  {  cout<<p->data<<"->";
	     p=p->next;
	  }
	  cout<<p->data<<endl;
   }
   for(i=1;i<=n;i++)
	   visited[i]=0;
   cout<<"請輸入開始訪問的頂點";
   cin>>i;
   cout<<endl;
   cout<<"從"<<i<<"出發的深度優先搜索遍歷序列為"<<endl;
   dfs1(i);
   cout<<endl;
}