// bo7-4.cpp 無向圖的鄰接多重表存儲(存儲結構由c7-4.h定義)的基本函數類型(16個)
 int LocateVex(AMLGraph G,VertexType u)
 { // 初始條件: 無向圖G存在,u和G中頂點有相同特征
   // 操作結果: 若G中存在頂點u,則返回該頂點在無向圖中位置;否則返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.adjmulist[i].data)==0)
       return i;
   return -1;
 }

 Status CreateGraph(AMLGraph &G)
 { // 采用鄰接多重表存儲結構,構造無向圖G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   EBox *p;
   printf("請輸入無向圖G的頂點數,邊數,邊是否含其它信息(是:1，否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.edgenum,&IncInfo);
   printf("請輸入%d個頂點的值(<%d個字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 構造頂點向量
   {
     scanf("%s",G.adjmulist[i].data);
     G.adjmulist[i].firstedge=NULL;
   }
   printf("請順序輸入每條邊的兩個端點(以空格作為間隔):\n");
   for(k=0;k<G.edgenum;++k) // 構造表結點鏈表
   {
     scanf("%s%s%*c",va,vb); // %*c吃掉回車符
     i=LocateVex(G,va); // 一端
     j=LocateVex(G,vb); // 另一端
     p=(EBox*)malloc(sizeof(EBox));
     p->mark=unvisited; // 設初值
     p->ivex=i;
     p->jvex=j;
     p->info=NULL;
     p->ilink=G.adjmulist[i].firstedge; // 插在表頭
     G.adjmulist[i].firstedge=p;
     p->jlink=G.adjmulist[j].firstedge; // 插在表頭
     G.adjmulist[j].firstedge=p;
     if(IncInfo) // 邊有相關信息
     {
       printf("請輸入該弧的相關信息(<%d個字符)：",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         p->info=(char*)malloc((l+1)*sizeof(char));
         strcpy(p->info,s);
       }
     }
   }
   return OK;
 }

 VertexType& GetVex(AMLGraph G,int v)
 { // 初始條件: 無向圖G存在,v是G中某個頂點的序號。操作結果: 返回v的值
   if(v>=G.vexnum||v<0)
     exit(ERROR);
   return G.adjmulist[v].data;
 }

 Status PutVex(AMLGraph &G,VertexType v,VertexType value)
 { // 初始條件: 無向圖G存在,v是G中某個頂點
   // 操作結果: 對v賦新值value
   int i;
   i=LocateVex(G,v);
   if(i<0) // v不是G的頂點
     return ERROR;
   strcpy(G.adjmulist[i].data,value);
   return OK;
 }

 int FirstAdjVex(AMLGraph G,VertexType v)
 { // 初始條件: 無向圖G存在,v是G中某個頂點
   // 操作結果: 返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1
   int i;
   i=LocateVex(G,v);
   if(i<0)
     return -1;
   if(G.adjmulist[i].firstedge) // v有鄰接頂點
     if(G.adjmulist[i].firstedge->ivex==i)
       return G.adjmulist[i].firstedge->jvex;
     else
       return G.adjmulist[i].firstedge->ivex;
   else
     return -1;
 }

 int NextAdjVex(AMLGraph G,VertexType v,VertexType w)
 { // 初始條件: 無向圖G存在,v是G中某個頂點,w是v的鄰接頂點
   // 操作結果: 返回v的(相對于w的)下一個鄰接頂點的序號。
   //           若w是v的最后一個鄰接點,則返回-1
   int i,j;
   EBox *p;
   i=LocateVex(G,v); // i是頂點v的序號
   j=LocateVex(G,w); // j是頂點w的序號
   if(i<0||j<0) // v或w不是G的頂點
     return -1;
   p=G.adjmulist[i].firstedge; // p指向頂點v的第1條邊
   while(p)
     if(p->ivex==i&&p->jvex!=j) // 不是鄰接頂點w(情況1)
       p=p->ilink; // 找下一個鄰接頂點
     else if(p->jvex==i&&p->ivex!=j) // 不是鄰接頂點w(情況2)
       p=p->jlink; // 找下一個鄰接頂點
     else // 是鄰接頂點w
       break;
   if(p&&p->ivex==i&&p->jvex==j) // 找到鄰接頂點w(情況1)
   {
     p=p->ilink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   if(p&&p->ivex==j&&p->jvex==i) // 找到鄰接頂點w(情況2)
   {
     p=p->jlink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   return -1;
 }

 Status InsertVex(AMLGraph &G,VertexType v)
 { // 初始條件: 無向圖G存在,v和G中頂點有相同特征
   // 操作結果: 在G中增添新頂點v(不增添與頂點相關的弧,留待InsertArc()去做)
   if(G.vexnum==MAX_VERTEX_NUM) // 結點已滿，不能插入
     return ERROR;
   if(LocateVex(G,v)>=0) // 結點已存在,不能插入
     return ERROR;
   strcpy(G.adjmulist[G.vexnum].data,v);
   G.adjmulist[G.vexnum].firstedge=NULL;
   G.vexnum++;
   return OK;
 }

 Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)
 { // 初始條件: 無向圖G存在,v和w是G中兩個頂點
   // 操作結果: 在G中刪除弧<v,w>
   int i,j;
   EBox *p,*q;
   i=LocateVex(G,v);
   j=LocateVex(G,w);
   if(i<0||j<0||i==j)
     return ERROR;  // 圖中沒有該點或弧
   // 以下使指向待刪除邊的第1個指針繞過這條邊
   p=G.adjmulist[i].firstedge; // p指向頂點v的第1條邊
   if(p&&p->jvex==j) // 第1條邊即為待刪除邊(情況1)
     G.adjmulist[i].firstedge=p->ilink;
   else if(p&&p->ivex==j) // 第1條邊即為待刪除邊(情況2)
     G.adjmulist[i].firstedge=p->jlink;
   else // 第1條邊不是待刪除邊
   {
     while(p) // 向后查找弧<v,w>
     {
       if(p->ivex==i&&p->jvex!=j) // 不是待刪除邊
       {
         q=p;
         p=p->ilink; // 找下一個鄰接頂點
       }
       else if(p->jvex==i&&p->ivex!=j) // 不是待刪除邊
       {
         q=p;
         p=p->jlink; // 找下一個鄰接頂點
       }
       else // 是鄰接頂點w
         break;
     }
     if(!p) // 沒找到該邊
       return ERROR;
     if(p->ivex==i&&p->jvex==j) // 找到弧<v,w>(情況1)
       if(q->ivex==i)
         q->ilink=p->ilink;
       else
         q->jlink=p->ilink;
     else if(p->ivex==j&&p->jvex==i) // 找到弧<v,w>(情況2)
       if(q->ivex==i)
         q->ilink=p->jlink;
       else
         q->jlink=p->jlink;
   }
   // 以下由另一頂點起找待刪除邊且刪除之
   p=G.adjmulist[j].firstedge; // p指向頂點w的第1條邊
   if(p->jvex==i) // 第1條邊即為待刪除邊(情況1)
   {
     G.adjmulist[j].firstedge=p->ilink;
     if(p->info) // 有相關信息
       free(p->info);
     free(p);
   }
   else if(p->ivex==i) // 第1條邊即為待刪除邊(情況2)
   {
     G.adjmulist[j].firstedge=p->jlink;
     if(p->info) // 有相關信息
       free(p->info);
     free(p);
   }
   else // 第1條邊不是待刪除邊
   {
     while(p) // 向后查找弧<v,w>
       if(p->ivex==j&&p->jvex!=i) // 不是待刪除邊
       {
         q=p;
         p=p->ilink; // 找下一個鄰接頂點
       }
       else if(p->jvex==j&&p->ivex!=i) // 不是待刪除邊
       {
         q=p;
         p=p->jlink; // 找下一個鄰接頂點
       }
       else // 是鄰接頂點v
         break;
     if(p->ivex==i&&p->jvex==j) // 找到弧<v,w>(情況1)
     {
       if(q->ivex==j)
         q->ilink=p->jlink;
       else
         q->jlink=p->jlink;
       if(p->info) // 有相關信息
         free(p->info);
       free(p);
     }
     else if(p->ivex==j&&p->jvex==i) // 找到弧<v,w>(情況2)
     {
       if(q->ivex==j)
         q->ilink=p->ilink;
       else
         q->jlink=p->ilink;
       if(p->info) // 有相關信息
         free(p->info);
       free(p);
     }
   }
   G.edgenum--;
   return OK;
 }

 Status DeleteVex(AMLGraph &G,VertexType v)
 { // 初始條件: 無向圖G存在,v是G中某個頂點
   // 操作結果: 刪除G中頂點v及其相關的邊
   int i,j;
   VertexType w;
   EBox *p;
   i=LocateVex(G,v); // i為待刪除頂點的序號
   if(i<0)
     return ERROR;
   for(j=0;j<G.vexnum;j++) // 刪除與頂點v相連的邊(如果有的話)
   {
     if(j==i)
       continue;
     strcpy(w,GetVex(G,j)); // w是第j個頂點的值
     DeleteArc(G,v,w);
   }
   for(j=i+1;j<G.vexnum;j++) // 排在頂點v后面的頂點的序號減1
     G.adjmulist[j-1]=G.adjmulist[j];
   G.vexnum--; // 頂點數減1
   for(j=i;j<G.vexnum;j++) // 修改頂點的序號
   {
     p=G.adjmulist[j].firstedge;
     if(p)
     {
       if(p->ivex==j+1)
       {
         p->ivex--;
         p=p->ilink;
       }
       else
       {
         p->jvex--;
         p=p->jlink;
       }
     }
   }
   return OK;
 }

 void DestroyGraph(AMLGraph &G)
 {
   int i;
   for(i=G.vexnum-1;i>=0;i--)
     DeleteVex(G,G.adjmulist[i].data);
 }

 Status InsertArc(AMLGraph &G,VertexType v,VertexType w)
 { // 初始條件: 無向圖G存在,v和W是G中兩個頂點
   // 操作結果: 在G中增添弧<v,w>
   int i,j,l,IncInfo;
   char s[MAX_INFO];
   EBox *p;
   i=LocateVex(G,v); // 一端
   j=LocateVex(G,w); // 另一端
   if(i<0||j<0)
     return ERROR;
   p=(EBox*)malloc(sizeof(EBox));
   p->mark=unvisited;
   p->ivex=i;
   p->jvex=j;
   p->info=NULL;
   p->ilink=G.adjmulist[i].firstedge; // 插在表頭
   G.adjmulist[i].firstedge=p;
   p->jlink=G.adjmulist[j].firstedge; // 插在表頭
   G.adjmulist[j].firstedge=p;
   printf("該邊是否有相關信息(1:有 0:無): ");
   scanf("%d%*c",&IncInfo); // %*c吃掉回車符
   if(IncInfo) // 邊有相關信息
   {
     printf("請輸入該邊的相關信息(<%d個字符)：",MAX_INFO);
     gets(s);
     l=strlen(s);
     if(l)
     {
       p->info=(char*)malloc((l+1)*sizeof(char));
       strcpy(p->info,s);
     }
   }
   G.edgenum++;
   return OK;
 }

 Boolean visite[MAX_VERTEX_NUM]; // 訪問標志數組(全局量)
 Status(*VisitFunc)(VertexType v);
 void DFS(AMLGraph G,int v)
 {
   int j;
   EBox *p;
   VisitFunc(G.adjmulist[v].data);
   visite[v]=TRUE;
   p=G.adjmulist[v].firstedge;
   while(p)
   {
     j=p->ivex==v?p->jvex:p->ivex;
     if(!visite[j])
       DFS(G,j);
     p=p->ivex==v?p->ilink:p->jlink;
   }
 }

 void DFSTraverse(AMLGraph G,Status(*visit)(VertexType))
 { // 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.4
   // 操作結果: 從第1個頂點起,深度優先遍歷圖G,并對每個頂點調用函數Visit
   //           一次且僅一次。一旦Visit()失敗,則操作失敗
   int v;
   VisitFunc=visit;
   for(v=0;v<G.vexnum;v++)
     visite[v]=FALSE;
   for(v=0;v<G.vexnum;v++)
     if(!visite[v])
       DFS(G,v);
   printf("\n");
 }

 typedef int QElemType; // 隊列類型
 #include"c3-2.h" // BFSTraverse()用
 #include"bo3-2.cpp" // BFSTraverse()用
 void BFSTraverse(AMLGraph G,Status(*Visit)(VertexType))
 { // 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.6
   // 操作結果: 從第1個頂點起,按廣度優先非遞歸遍歷圖G,并對每個頂點調用函數
   //           Visit一次且僅一次。一旦Visit()失敗,則操作失敗。
   //           使用輔助隊列Q和訪問標志數組visite
   int v,u,w;
   VertexType w1,u1;
   LinkQueue Q;
   for(v=0;v<G.vexnum;v++)
     visite[v]=FALSE; // 置初值
   InitQueue(Q); // 置空的輔助隊列Q
   for(v=0;v<G.vexnum;v++)
     if(!visite[v]) // v尚未訪問
     {
       visite[v]=TRUE; // 設置訪問標志為TRUE(已訪問)
       Visit(G.adjmulist[v].data);
       EnQueue(Q,v); // v入隊列
       while(!QueueEmpty(Q)) // 隊列不空
       {
         DeQueue(Q,u); // 隊頭元素出隊并置為u
         strcpy(u1,GetVex(G,u));
         for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,GetVex(G,w))))
           if(!visite[w]) // w為u的尚未訪問的鄰接頂點的序號
           {
             visite[w]=TRUE;
             Visit(G.adjmulist[w].data);
             EnQueue(Q,w);
           }
       }
     }
   printf("\n");
 }

 void MarkUnvizited(AMLGraph G)
 { // 置邊的訪問標記為未被訪問
   int i;
   EBox *p;
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
     {
       p->mark=unvisited;
       if(p->ivex==i)
         p=p->ilink;
       else
         p=p->jlink;
     }
   }
 }

 void Display(AMLGraph G)
 { // 輸出無向圖的鄰接多重表G
   int i;
   EBox *p;
   MarkUnvizited(G); // 置邊的訪問標記為未被訪問
   printf("%d個頂點：\n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     printf("%s ",G.adjmulist[i].data);
   printf("\n%d條邊:\n",G.edgenum);
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
       if(p->ivex==i) // 邊的i端與該頂點有關
       {
         if(!p->mark) // 只輸出一次
         {
           printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
           p->mark=visited;
           if(p->info) // 輸出附帶信息
             printf("相關信息: %s ",p->info);
         }
         p=p->ilink;
       }
       else // 邊的j端與該頂點有關
       {
         if(!p->mark) // 只輸出一次
         {
           printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
           p->mark=visited;
           if(p->info) // 輸出附帶信息
             printf("相關信息: %s ",p->info);
         }
         p=p->jlink;
       }
     printf("\n");
   }
 }