//用鄰接矩陣實現無向圖的深度優先搜索遍歷
#include<iostream.h>
const  int  n=8;                    // 圖中頂點數  
const  int  e=10;
typedef int elemtype;                    // 圖中邊數
struct    graph
{  
elemtype       v[n+1];                  // 存放頂點信息v1,v2,….vn，不使用v[0]存儲空間
int    arcs[n+1][n+1];             // 鄰接矩陣
};

graph  g;
int visited[n+1];
void  creatadj( )
{ int i,j,k ;
  cout<<"請輸入頂點信息"<<endl;
  for  (k=1; k<=n; k++)
  cin>>g.v[k];                            //輸入頂點信息   
for (i=1; i<=n;  i++ )
  for (j=1; j<=n; j++)
   g.arcs[i][j]=0;
for (k=1; k<=e; k++)
{    cout<<"請輸入一條邊";
	cin>>i>>j;                             //輸入一條邊(i,j)           
    cout<<endl;
	g.arcs[i][j]=1;
    g.arcs[j][i]=1;
}
}
void dfs (int i)                             // 從頂點i 出發遍歷
{  
 int j;                                                           
           cout<<g.v[i]<<"  ";                        //輸出訪問頂點
           visited[i]=1;        //全局數組訪問標記置1表示已經訪問
            for(j=1; j<=n; j++)
				if ((g.arcs[i][j]==1)&&(!visited[j]))
                    dfs(j);
        }

void main( )
{  int i,j;
    for(i=1;i<=n;i++)
		visited[i]=0;
	creatadj( );
	for(i=1;i<=n;i++)
	{for(j=1;j<=n;j++)
			cout<<g.arcs[i][j]<<"  ";
	cout<<endl;
	}
	cout<<"請輸入開始訪問的頂點";
	cin>>i;
	cout<<endl;
	cout<<"從"<<i<<"出發的深度優先搜索遍歷序列為"<<endl;
	dfs(i);
    cout<<endl;
}