#include <stdio.h> 
#include <malloc.h> 

#define INFINITY 32767 
#define MAX_VEX 20 //最大頂點(diǎn)個(gè)數(shù) 

bool *visited; //訪問標(biāo)志數(shù)組 

//圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) 
typedef struct{ 
char *vexs; //頂點(diǎn)向量 
int arcs[MAX_VEX][MAX_VEX]; //鄰接矩陣 
int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) 
}Graph; 


//圖G中查找元素c的位置 
int Locate(Graph G,char c){ 
for(int i=0;i<G.vexnum;i++) 
if(G.vexs[i]==c) return i; 
return -1; 
} 

//創(chuàng)建無向網(wǎng) 
void CreateUDN(Graph &G){ 
int i,j,k,w,s1,s2; 
char a,b,temp; 
printf("輸入頂點(diǎn)數(shù)和弧數(shù):"); 
scanf("%d%d",&G.vexnum,&G.arcnum); 
temp=getchar(); //接收回車 
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配頂點(diǎn)數(shù)目 

printf("輸入%d個(gè)頂點(diǎn).\n",G.vexnum); 
for(i=0;i<G.vexnum;i++){ //初始化頂點(diǎn) 
printf("輸入頂點(diǎn)%d:",i); 
scanf("%c",&G.vexs[i]); 
temp=getchar(); //接收回車 
} 

for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣 
for(j=0;j<G.vexnum;j++) 
G.arcs[i][j]=INFINITY; 

printf("輸入%d條弧.\n",G.arcnum); 
for(i=0;i<G.arcnum;i++){ //初始化弧 
printf("輸入弧%d:",i); 
scanf("%c %c %d",&a,&b,&w); //輸入一條邊依附的頂點(diǎn)和權(quán)值 
temp=getchar(); //接收回車 
s1=Locate(G,a); 
s2=Locate(G,b); 
G.arcs[s1][s2]=G.arcs[s2][s1]=w; 
} 
} 

//圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn) 
int FirstVex(Graph G,int k){ 
if(k>=0 && k<G.vexnum){ //k合理 
for(int i=0;i<G.vexnum;i++) 
if(G.arcs[k][i]!=INFINITY) return i; 
} 
return -1; 
} 

//圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) 
int NextVex(Graph G,int i,int j){ 
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理 for(int k=j+1;k<G.vexnum;k++) 
if(G.arcs[i][k]!=INFINITY) return k; 
} 
return -1; 
} 

//深度優(yōu)先遍歷 
void DFS(Graph G,int k){ 
int i; 
if(k==-1){ //第一次執(zhí)行DFS時(shí),k為-1 
for(i=0;i<G.vexnum;i++) 
if(!visited[i]) DFS(G,i); //對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS 
} 
else{ 
visited[k]=true; 
printf("%c ",G.vexs[k]); //訪問第k個(gè)頂點(diǎn) 
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) 
if(!visited[i]) DFS(G,i); //對(duì)k的尚未訪問的鄰接頂點(diǎn)i遞歸調(diào)用DFS 
} 
} 

//主函數(shù) 
void main(){ 
int i; 
Graph G; 
CreateUDN(G); 
visited=(bool *)malloc(G.vexnum*sizeof(bool)); 
printf("\n深度優(yōu)先遍歷: "); 
for(i=0;i<G.vexnum;i++) 
visited[i]=false; 
DFS(G,-1); 
printf("\n程序結(jié)束.\n"); 
}