#include <stdio.h>
#include <string.h>
#define INFINITY INT_MAX  999
#define MAX_VERTEX_NUM  20

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*矩陣類型*/

typedef char VexType[10];  /*頂點類型*/

typedef struct
{   VexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
int kind;  /*圖的種類：1-無向圖 2-無向網 3-有向圖 4-有向網*/
}MGraph; /*圖的類型*/

int LocateVex(MGraph &G,VexType v);

void CreatUDG(MGraph &G) /*無向圖的創建操作*/
{  VexType v1,v2;
   int i,j,k;
   G.kind=1;
   printf("Input vertex number and edg number:");
   scanf("%d%d",&G.vexnum,&G.arcnum);
   printf("Input vertexs:\n");
   for(i=0;i<G.vexnum;++i)  scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i)
      for(j=0;j<G.vexnum;++j) G.arcs[i][j]=0;
   for(k=0;k<G.arcnum;++k) 
  { 
     printf("Input edge(v1 v2):");
     scanf("%s%s",v1,v2);
     i=LocateVex(G,v1);
     if(i==-1) { printf(" Error!\n"); return;}
     j=LocateVex(G,v2);
     if(j==-1) {  printf(" Error!\n"); return;}
     G.arcs[i][j]=G.arcs[j][i]=1;
  }   
}

int LocateVex(MGraph &G,VexType v) /*在圖G中查找頂點v，若存在返回位置，否則返回-1*/
{  int i;
   for(i=0;i<G.vexnum;i++)
     if(strcmp(G.vexs[i],v)==0) return i;
   return -1;
}

  void GraphOutput(MGraph &G)/*圖的鄰接矩陣的輸出操作*/
{  int i,j;
   printf("\t");
   for(i=0;i<G.vexnum;++i)
      printf("%8s",G.vexs[i]);
   printf("\n");
   for(i=0;i<G.vexnum;++i)
   {  printf("%s\t",G.vexs[i]);
      for(j=0;j<G.vexnum;++j) 
         printf("%8d",G.arcs[i][j]);
      printf("\n");
   }
}

int FirstAdjVex(MGraph &G, int v)/*求v的第一個鄰接頂點*/
{ /*代碼略*/}
int NextAdjVex(MGraph &G, int v,int w) /*求v的相對于w的下一個鄰接頂點*/
{ /*代碼略*/}

void DFSTraverse(MGraph &G,int v)/*圖的深度優先遍歷算法*/
{VisitFunc=Visit;
for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
for (v=0;v<G.vexnum;++v)
  if(!visited[v]) DFS(G,v);
}

void DFS(Graph G,int v)
{visited[v]=TRUE;VisitFunc(v);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);}

void BFSTraverse(MGraph &G)/*圖的廣度優先遍歷算法*/
{for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
	if (!visited[v]){
	  visited[v]=TRUE;Visit(v);
	  EnQueue(Q,v);
          while(!QueueEmpty(Q)){
		DeQueue(Q,u);
		for(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))
			if (!Visited[w])
			   {Visited[w]=TRUE;Visit(w);
			    EnQueue(Q,w);}
                               }
          }
}

/*其他操作略*/

main()
{  MGraph G;
   CreatUDG(G);
   GraphOutput(G);
   DFSTraverse(G);
   BFSTraverse(G);
}