第七章 圖 7.14 Status Build_AdjList(ALGraph &G)/輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接表  InitALGraph(G);  scanf("%d",&v);  if(v<0) return ERROR; /頂點(diǎn)數(shù)不能為負(fù)  G.vexnum=v;  scanf("%d",&a);  if(a<0) return ERROR; /邊數(shù)不能為負(fù)  G.arcnum=a;  for(m=0;m<v;m+)    G.verticesm.data=getchar(); /輸入各頂點(diǎn)的符號(hào)  for(m=1;m<=a;m+)      t=getchar();h=getchar(); /t為弧尾,h為弧頭    if(i=LocateVex(G,t)<0) return ERROR;    if(j=LocateVex(G,h)<0) return ERROR; /頂點(diǎn)未找到    p=(ArcNode*)malloc(sizeof(ArcNode);    if(!G.vertices.i.firstarc) G.verticesi.firstarc=p;    else          for(q=G.verticesi.firstarc;q->nextarc;q=q->nextarc);      q->nextarc=p;        p->adjvex=j;p->nextarc=NULL;  /while  return OK;/Build_AdjList 7.15 /本題中的圖G均為有向無權(quán)圖,其余情況容易由此寫出Status Insert_Vex(MGraph &G, char v)/在鄰接矩陣表示的圖G上插入頂點(diǎn)v  if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;  G.vexs+G.vexnum=v;  return OK;/Insert_Vex Status Insert_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上插入邊(v,w)  if(i=LocateVex(G,v)<0) return ERROR;  if(j=LocateVex(G,w)<0) return ERROR;  if(i=j) return ERROR;  if(!G.arcsij.adj)      G.arcsij.adj=1;    G.arcnum+;    return OK;/Insert_Arc Status Delete_Vex(MGraph &G,char v)/在鄰接矩陣表示的圖G上刪除頂點(diǎn)v  n=G.vexnum;  if(m=LocateVex(G,v)<0) return ERROR;  G.vexsm<->G.vexsn; /將待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)  for(i=0;i<n;i+)      G.arcsim=G.arcsin;    G.arcsmi=G.arcsni; /將邊的關(guān)系隨之交換    G.arcsmm.adj=0;  G.vexnum-;  return OK;/Delete_Vex分析:如果不把待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn)的話,算法將會(huì)比較復(fù)雜,而伴隨著大量元素的移動(dòng),時(shí)間復(fù)雜度也會(huì)大大增加. Status Delete_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上刪除邊(v,w)  if(i=LocateVex(G,v)<0) return ERROR;  if(j=LocateVex(G,w)<0) return ERROR;  if(G.arcsij.adj)      G.arcsij.adj=0;    G.arcnum-;    return OK;/Delete_Arc 7.16 /為節(jié)省篇幅,本題只給出Insert_Arc算法.其余算法請(qǐng)自行寫出. Status Insert_Arc(ALGraph &G,char v,char w)/在鄰接表表示的圖G上插入邊(v,w)  if(i=LocateVex(G,v)<0) return ERROR;  if(j=LocateVex(G,w)<0) return ERROR;  p=(ArcNode*)malloc(sizeof(ArcNode);  p->adjvex=j;p->nextarc=NULL;  if(!G.verticesi.firstarc) G.verticesi.firstarc=p;  else      for(q=G.verticesi.firstarc;q->q->nextarc;q=q->nextarc)      if(q->adjvex=j) return ERROR; /邊已經(jīng)存在    q->nextarc=p;    G.arcnum+;  return OK;/Insert_Arc 7.17 /為節(jié)省篇幅,本題只給出較為復(fù)雜的Delete_Vex算法.其余算法請(qǐng)自行寫出. Status Delete_Vex(OLGraph &G,char v)/在十字鏈表表示的圖G上刪除頂點(diǎn)v  if(m=LocateVex(G,v)<0) return ERROR;  n=G.vexnum;  for(i=0;i<n;i+) /刪除所有以v為頭的邊      if(G.xlisti.firstin->tailvex=m) /如果待刪除的邊是頭鏈上的第一個(gè)結(jié)點(diǎn)          q=G.xlisti.firstin;      G.xlisti.firstin=q->hlink;      free(q);G.arcnum-;        else /否則          for(p=G.xlisti.firstin;p&&p->hlink->tailvex!=m;p=p->hlink);      if(p)              q=p->hlink;        p->hlink=q->hlink;        free(q);G.arcnum-;          /else  /for  for(i=0;i<n;i+) /刪除所有以v為尾的邊      if(G.xlisti.firstout->headvex=m) /如果待刪除的邊是尾鏈上的第一個(gè)結(jié)點(diǎn)          q=G.xlisti.firstout;      G.xlisti.firstout=q->tlink;      free(q);G.arcnum-;        else /否則          for(p=G.xlisti.firstout;p&&p->tlink->headvex!=m;p=p->tlink);      if(p)              q=p->tlink;        p->tlink=q->tlink;        free(q);G.arcnum-;          /else  /for  for(i=m;i<n;i+) /順次用結(jié)點(diǎn)m之后的頂點(diǎn)取代前一個(gè)頂點(diǎn)      G.xlisti=G.xlisti+1; /修改表頭向量    for(p=G.xlisti.firstin;p;p=p->hlink)      p->headvex-;    for(p=G.xlisti.firstout;p;p=p->tlink)      p->tailvex-; /修改各鏈中的頂點(diǎn)序號(hào)    G.vexnum-;  return OK;/Delete_Vex 7.18 /為節(jié)省篇幅,本題只給出Delete_Arc算法.其余算法請(qǐng)自行寫出. Status Delete_Arc(AMLGraph &G,char v,char w)/在鄰接多重表表示的圖G上刪除邊(v,w)  if(i=LocateVex(G,v)<0) return ERROR;  if(j=LocateVex(G,w)<0) return ERROR;  if(G.adjmulisti.firstedge->jvex=j)    G.adjmulisti.firstedge=G.adjmulisti.firstedge->ilink;  else      for(p=G.adjmulisti.firstedge;p&&p->ilink->jvex!=j;p=p->ilink);    if (!p) return ERROR; /未找到    p->ilink=p->ilink->ilink;   /在i鏈表中刪除該邊  if(G.adjmulistj.firstedge->ivex=i)    G.adjmulistj.firstedge=G.adjmulistj.firstedge->jlink;  else      for(p=G.adjmulistj.firstedge;p&&p->jlink->ivex!=i;p=p->jlink);    if (!p) return ERROR; /未找到    q=p->jlink;    p->jlink=q->jlink;    free(q);   /在i鏈表中刪除該邊  G.arcnum-;  return OK;/Delete_Arc 7.19 Status Build_AdjMulist(AMLGraph &G)/輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接多重表  InitAMLGraph(G);  scanf("%d",&v);  if(v<0) return ERROR; /頂點(diǎn)數(shù)不能為負(fù)  G.vexnum=v;  scanf(%d",&a);  if(a<0) return ERROR; /邊數(shù)不能為負(fù)  G.arcnum=a;  for(m=0;m<v;m+)    G.adjmulistm.data=getchar(); /輸入各頂點(diǎn)的符號(hào)  for(m=1;m<=a;m+)      t=getchar();h=getchar(); /t為弧尾,h為弧頭    if(i=LocateVex(G,t)<0) return ERROR;    if(j=LocateVex(G,h)<0) return ERROR; /頂點(diǎn)未找到    p=(EBox*)malloc(sizeof(EBox);    p->ivex=i;p->jvex=j;    p->ilink=NULL;p->jlink=NULL; /邊結(jié)點(diǎn)賦初值    if(!G.adjmulisti.firstedge) G.adjmulisti.firstedge=p;    else          q=G.adjmulisti.firstedge;      while(q)              r=q;        if(q->ivex=i) q=q->ilink;        else q=q->jlink;            if(r->ivex=i) r->ilink=p;/注意i值既可能出現(xiàn)在邊結(jié)點(diǎn)的ivex域中,      else r->jlink=p; /又可能出現(xiàn)在邊結(jié)點(diǎn)的jvex域中    /else /插入i鏈表尾部    if(!G.adjmulistj.firstedge) G.adjmulistj.firstedge=p;    else          q=G.adjmulisti.firstedge;      while(q)              r=q;        if(q->jvex=j) q=q->jlink;        else q=q->ilnk;            if(r->jvex=j) r->jlink=p;      else r->ilink=p;    /else /插入j鏈表尾部  /for  return OK;/Build_AdjList 7.20 int Pass_MGraph(MGraph G)/判斷一個(gè)鄰接矩陣存儲(chǔ)的有向圖是不是可傳遞的,是則返回1,否則返回0  for(x=0;x<G.vexnum;x+)    for(y=0;y<G.vexnum;y+)      if(G.arcsxy)              for(z=0;z<G.vexnum;z+)          if(z!=x&&G.arcsyz&&!G.arcsxz) return 0;/圖不可傳遞的條件      /if  return 1;/Pass_MGraph分析:本算法的時(shí)間復(fù)雜度大概是O(n2*d). 7.21 int Pass_ALGraph(ALGraph G)/判斷一個(gè)鄰接表存儲(chǔ)的有向圖是不是可傳遞的,是則返回1,否則返回0  for(x=0;x<G.vexnum;x+)    for(p=G.verticesx.firstarc;p;p=p->nextarc)          y=p->adjvex;      for(q=G.verticesy.firstarc;q;q=q->nextarc)              z=q->adjvex;        if(z!=x&&!is_adj(G,x,z) return 0;      /for    /for/Pass_ALGraph int is_adj(ALGraph G,int m,int n)/判斷有向圖G中是否存在邊(m,n),是則返回1,否則返回0  for(p=G.verticesm.firstarc;p;p=p->nextarc)    if(p->adjvex=n) return 1;  return 0;/is_adj 7.22 int visitedMAXSIZE; /指示頂點(diǎn)是否在當(dāng)前路徑上 int exist_path_DFS(ALGraph G,int i,int j)/深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0  if(i=j) return 1; /i就是j  else      visitedi=1;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          k=p->adjvex;      if(!visitedk&&exist_path(k,j) return 1;/i下游的頂點(diǎn)到j(luò)有路徑    /for  /else/exist_path_DFS 7.23 int exist_path_BFS(ALGraph G,int i,int j)/廣度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0  int visitedMAXSIZE;  InitQueue(Q);  EnQueue(Q,i);  while(!QueueEmpty(Q)      DeQueue(Q,u);    visitedu=1;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          k=p->adjvex;      if(k=j) return 1;      if(!visitedk) EnQueue(Q,k);    /for  /while  return 0;/exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)/非遞歸遍歷強(qiáng)連通圖G  int visitedMAXSIZE;  InitStack(S);  Push(S,GetVex(S,1); /將第一個(gè)頂點(diǎn)入棧  visit(1);  visited=1;  while(!StackEmpty(S)      while(Gettop(S,i)&&i)          j=FirstAdjVex(G,i);      if(j&&!visitedj)              visit(j);        visitedj=1;        Push(S,j); /向左走到盡頭          /while    if(!StackEmpty(S)          Pop(S,j);      Gettop(S,i);      k=NextAdjVex(G,i,j); /向右走一步      if(k&&!visitedk)              visit(k);        visitedk=1;        Push(S,k);          /if  /while/Straverse_Nonrecursive分析:本算法的基本思想與二叉樹的先序遍歷非遞歸算法相同,請(qǐng)參考6.37.由于是強(qiáng)連通圖,所以從第一個(gè)結(jié)點(diǎn)出發(fā)一定能夠訪問到所有結(jié)點(diǎn). 7.25 見書后解答. 7.26 Status TopoNo(ALGraph G)/按照題目要求順序重排有向圖中的頂點(diǎn)  int newMAXSIZE,indegreeMAXSIZE; /儲(chǔ)存結(jié)點(diǎn)的新序號(hào)  n=G.vexnum;  FindInDegree(G,indegree);  InitStack(S);  for(i=1;i<G.vexnum;i+)    if(!indegreei) Push(S,i); /零入度結(jié)點(diǎn)入棧  count=0;  while(!StackEmpty(S)      Pop(S,i);    newi=n-; /記錄結(jié)點(diǎn)的拓?fù)淠嫘蛐蛱?hào)    count+;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          k=p->adjvex;      if(!(-indegreek) Push(S,k);    /for  /while  if(count<G.vexnum) return ERROR; /圖中存在環(huán)  for(i=1;i<=n;i+) printf("Old No:%d New No:%dn",i,newi)  return OK;/TopoNo分析:只要按拓?fù)淠嫘驅(qū)旤c(diǎn)編號(hào),就可以使鄰接矩陣成為下三角矩陣. 7.27 int visitedMAXSIZE; int exist_path_len(ALGraph G,int i,int j,int k)/判斷鄰接表方式存儲(chǔ)的有向圖G的頂點(diǎn)i到j(luò)是否存在長(zhǎng)度為k的簡(jiǎn)單路徑  if(i=j&&k=0) return 1; /找到了一條路徑,且長(zhǎng)度符合要求  else if(k>0)      visitedi=1;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          l=p->adjvex;      if(!visitedl)        if(exist_path_len(G,l,j,k-1) return 1; /剩余路徑長(zhǎng)度減一    /for    visitedi=0; /本題允許曾經(jīng)被訪問過的結(jié)點(diǎn)出現(xiàn)在另一條路徑中  /else  return 0; /沒找到/exist_path_len 7.28 int pathMAXSIZE,visitedMAXSIZE; /暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k)/求有向圖G中頂點(diǎn)u到v之間的所有簡(jiǎn)單路徑,k表示當(dāng)前路徑長(zhǎng)度  pathk=u; /加入當(dāng)前路徑中  visitedu=1;  if(u=v) /找到了一條簡(jiǎn)單路徑      printf("Found one path!n");    for(i=0;pathi;i+) printf("%d",pathi); /打印輸出    else    for(p=G.verticesu.firstarc;p;p=p->nextarc)          l=p->adjvex;      if(!visitedl) Find_All_Path(G,l,v,k+1); /繼續(xù)尋找      visitedu=0;  pathk=0; /回溯/Find_All_Path main()  .  Find_All_Path(G,u,v,0); /在主函數(shù)中初次調(diào)用,k值應(yīng)為0  ./main 7.29 int GetPathNum_Len(ALGraph G,int i,int j,int len)/求鄰接表方式存儲(chǔ)的有向圖G的頂點(diǎn)i到j(luò)之間長(zhǎng)度為len的簡(jiǎn)單路徑條數(shù)  if(i=j&&len=0) return 1; /找到了一條路徑,且長(zhǎng)度符合要求  else if(len>0)      sum=0; /sum表示通過本結(jié)點(diǎn)的路徑數(shù)    visitedi=1;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          l=p->adjvex;      if(!visitedl)        sum+=GetPathNum_Len(G,l,j,len-1)/剩余路徑長(zhǎng)度減一    /for    visitedi=0; /本題允許曾經(jīng)被訪問過的結(jié)點(diǎn)出現(xiàn)在另一條路徑中  /else  return sum;/GetPathNum_Len 7.30 int visitedMAXSIZE;int pathMAXSIZE; /暫存當(dāng)前路徑int cyclesMAXSIZEMAXSIZE; /儲(chǔ)存發(fā)現(xiàn)的回路所包含的結(jié)點(diǎn)int thiscycleMAXSIZE; /儲(chǔ)存當(dāng)前發(fā)現(xiàn)的一個(gè)回路int cycount=0; /已發(fā)現(xiàn)的回路個(gè)數(shù) void GetAllCycle(ALGraph G)/求有向圖中所有的簡(jiǎn)單回路  for(v=0;v<G.vexnum;v+) visitedv=0;  for(v=0;v<G.vexnum;v+)    if(!visitedv) DFS(G,v,0); /深度優(yōu)先遍歷/DFSTraverse void DFS(ALGraph G,int v,int k)/k表示當(dāng)前結(jié)點(diǎn)在路徑上的序號(hào)  visitedv=1;  pathk=v; /記錄當(dāng)前路徑  for(p=G.verticesv.firstarc;p;p=p->nextarc)      w=p->adjvex;    if(!visitedw) DFS(G,w,k+1);    else /發(fā)現(xiàn)了一條回路          for(i=0;pathi!=w;i+); /找到回路的起點(diǎn)      for(j=0;pathi+j;i+) thiscyclej=pathi+j;/把回路復(fù)制下來      if(!exist_cycle() cyclescycount+=thiscycle;/如果該回路尚未被記錄過,就添加到記錄中      for(i=0;i<G.vexnum;i+) thiscyclei=0; /清空目前回路數(shù)組    /else  /for  pathk=0;  visitedk=0; /注意只有當(dāng)前路徑上的結(jié)點(diǎn)visited為真.因此一旦遍歷中發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)visited為真,即表示發(fā)現(xiàn)了一條回路/DFS int exist_cycle()/判斷thiscycle數(shù)組中記錄的回路在cycles的記錄中是否已經(jīng)存在  int tempMAXSIZE;  for(i=0;i<cycount;i+) /判斷已有的回路與thiscycle是否相同   /也就是,所有結(jié)點(diǎn)和它們的順序都相同    j=0;c=thiscycle&#0; /例如,142857和857142是相同的回路    for(k=0;cyclesik!=c&&cyclesik!=0;k+);/在cycles的一個(gè)行向量中尋找等于thiscycle第一個(gè)結(jié)點(diǎn)的元素    if(cyclesik) /有與之相同的一個(gè)元素          for(m=0;cyclesik+m;m+)        tempm=cyclesik+m;      for(n=0;n<k;n+,m+)        tempm=cyclesin; /調(diào)整cycles中的當(dāng)前記錄的循環(huán)相位并放入temp數(shù)組中      if(!StrCompare(temp,thiscycle) /與thiscycle比較        return 1; /完全相等      for(m=0;m<G.vexnum;m+) tempm=0; /清空這個(gè)數(shù)組      /for  return 0; /所有現(xiàn)存回路都不與thiscycle完全相等/exist_cycle分析:這個(gè)算法的思想是,在遍歷中暫存當(dāng)前路徑,當(dāng)遇到一個(gè)結(jié)點(diǎn)已經(jīng)在路徑之中時(shí)就表明存在一條回路;掃描路徑向量path可以獲得這條回路上的所有結(jié)點(diǎn).把結(jié)點(diǎn)序列(例如,142857)存入thiscycle中;由于這種算法中,一條回路會(huì)被發(fā)現(xiàn)好幾次,所以必須先判斷該回路是否已經(jīng)在cycles中被記錄過,如果沒有才能存入cycles的一個(gè)行向量中.把cycles的每一個(gè)行向量取出來與之比較.由于一條回路可能有多種存儲(chǔ)順序,比如142857等同于285714和571428,所以還要調(diào)整行向量的次序,并存入temp數(shù)組,例如,thiscycle為142857第一個(gè)結(jié)點(diǎn)為1,cycles的當(dāng)前向量為857142,則找到后者中的1,把1后部分提到1前部分前面,最終在temp中得到142857,與thiscycle比較,發(fā)現(xiàn)相同,因此142857和857142是同一條回路,不予存儲(chǔ).這個(gè)算法太復(fù)雜,很難保證細(xì)節(jié)的準(zhǔn)確性,大家理解思路便可.希望有人給出更加簡(jiǎn)捷的算法. 7.31 int visitedMAXSIZE;int finishedMAXSIZE;int count; /count在第一次深度優(yōu)先遍歷中用于指示finished數(shù)組的填充位置 void Get_SGraph(OLGraph G)/求十字鏈表結(jié)構(gòu)儲(chǔ)存的有向圖G的強(qiáng)連通分量  count=0;  for(v=0;v<G.vexnum;v+) visitedv=0;  for(v=0;v<G.vexnum;v+) /第一次深度優(yōu)先遍歷建立finished數(shù)組    if(!visitedv) DFS1(G,v);  for(v=0;v<G.vexnum;v+) visitedv=0; /清空visited數(shù)組  for(i=G.vexnum-1;i>=0;i-) /第二次逆向的深度優(yōu)先遍歷      v=finished(i);    if(!visitedv)          printf("n"); /不同的強(qiáng)連通分量在不同的行輸出      DFS2(G,v);      /for/Get_SGraph void DFS1(OLGraph G,int v)/第一次深度優(yōu)先遍歷的算法  visitedv=1;  for(p=G.xlistv.firstout;p;p=p->tlink)      w=p->headvex;    if(!visitedw) DFS1(G,w);  /for  finished+count=v; /在第一次遍歷中建立finished數(shù)組/DFS1 void DFS2(OLGraph G,int v)/第二次逆向的深度優(yōu)先遍歷的算法  visitedv=1;  printf("%d",v); /在第二次遍歷中輸出結(jié)點(diǎn)序號(hào)  for(p=G.xlistv.firstin;p;p=p->hlink)      w=p->tailvex;    if(!visitedw) DFS2(G,w);  /for/DFS2分析:求有向圖的強(qiáng)連通分量的算法的時(shí)間復(fù)雜度和深度優(yōu)先遍歷相同,也為O(n+e). 7.32 void Forest_Prim(ALGraph G,int k,CSTree &T)/從頂點(diǎn)k出發(fā),構(gòu)造鄰接表結(jié)構(gòu)的有向圖G的最小生成森林T,用孩子兄弟鏈表存儲(chǔ)  for(j=0;j<G.vexnum;j+) /以下在Prim算法基礎(chǔ)上稍作改動(dòng)    if(j!=k)          closedgej=k,Max_int;      for(p=G.verticesj.firstarc;p;p=p->nextarc)        if(p->adjvex=k) closedgej.lowcost=p->cost;    /if  closedgek.lowcost=0;  for(i=1;i<G.vexnum;i+)      k=minimum(closedge);    if(closedgek.lowcost<Max_int)          Addto_Forest(T,closedgek.adjvex,k); /把這條邊加入生成森林中      closedgek.lowcost=0;      for(p=G.verticesk.firstarc;p;p=p->nextarc)        if(p->cost<closedgep->adjvex.lowcost)          closedgep->adjvex=k,p->cost;    /if    else Forest_Prim(G,k); /對(duì)另外一個(gè)連通分量執(zhí)行算法  /for/Forest_Prim void Addto_Forest(CSTree &T,int i,int j)/把邊(i,j)添加到孩子兄弟鏈表表示的樹T中  p=Locate(T,i); /找到結(jié)點(diǎn)i對(duì)應(yīng)的指針p,過程略  q=(CSTNode*)malloc(sizeof(CSTNode);  q->data=j;  if(!p) /起始頂點(diǎn)不屬于森林中已有的任何一棵樹      p=(CSTNode*)malloc(sizeof(CSTNode);    p->data=i;    for(r=T;r->nextsib;r=r->nextsib);    r->nextsib=p;    p->firstchild=q;   /作為新樹插入到最右側(cè)  else if(!p->firstchild) /雙親還沒有孩子    p->firstchild=q; /作為雙親的第一個(gè)孩子  else /雙親已經(jīng)有了孩子      for(r=p->firstchild;r->nextsib;r=r->nextsib);    r->nextsib=q; /作為雙親最后一個(gè)孩子的兄弟  /Addto_Forest main()  .  T=(CSTNode*)malloc(sizeof(CSTNode); /建立樹根  T->data=1;  Forest_Prim(G,1,T);  ./main分析:這個(gè)算法是在Prim算法的基礎(chǔ)上添加了非連通圖支持和孩子兄弟鏈表構(gòu)建模塊而得到的,其時(shí)間復(fù)雜度為O(n2). 7.33 typedef struct                   int vex; /結(jié)點(diǎn)序號(hào)                  int ecno; /結(jié)點(diǎn)所屬的連通分量號(hào)                VexInfo;VexInfo vexsMAXSIZE; /記錄結(jié)點(diǎn)所屬連通分量號(hào)的數(shù)組 void Init_VexInfo(VexInfo &vexs ,int vexnum)/初始化  for(i=0;i<vexnum;i+)    vexsi=i,i; /初始狀態(tài):每一個(gè)結(jié)點(diǎn)都屬于不同的連通分量/Init_VexInfo int is_ec(VexInfo vexs ,int i,int j)/判斷頂點(diǎn)i和頂點(diǎn)j是否屬于同一個(gè)連通分量  if(vexsi.ecno=vexsj.ecno) return 1;  else return 0;/is_ec void merge_ec(VexInfo &vexs ,int ec1,int ec2)/合并連通分量ec1和ec2  for(i=0;vexsi.vex;i+)    if(vexsi.ecno=ec2) vexsi.ecno=ec1;/merge_ec void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T)/求圖的最小生成樹的克魯斯卡爾算法  Init_VexInfo(vexs,G.vexnum);  ecnum=G.vexnum; /連通分量個(gè)數(shù)  while(ecnum>1)      GetMinEdge(EdgeSet,u,v); /選出最短邊    if(!is_ec(vexs,u,v) /u和v屬于不同連通分量          Addto_CSTree(T,u,v); /加入到生成樹中      merge_ec(vexs,vexsu.ecno,vexsv.ecno); /合并連通分量      ecnum-;        DelMinEdge(EdgeSet,u,v); /從邊集中刪除  /while/MinSpanTree_Kruscal void Addto_CSTree(CSTree &T,int i,int j)/把邊(i,j)添加到孩子兄弟鏈表表示的樹T中  p=Locate(T,i); /找到結(jié)點(diǎn)i對(duì)應(yīng)的指針p,過程略  q=(CSTNode*)malloc(sizeof(CSTNode);  q->data=j;  if(!p->firstchild) /雙親還沒有孩子    p->firstchild=q; /作為雙親的第一個(gè)孩子  else /雙親已經(jīng)有了孩子      for(r=p->firstchild;r->nextsib;r=r->nextsib);    r->nextsib=q; /作為雙親最后一個(gè)孩子的兄弟  /Addto_CSTree分析:本算法使用一維結(jié)構(gòu)體變量數(shù)組來表示等價(jià)類,每個(gè)連通分量所包含的所有結(jié)點(diǎn)屬于一個(gè)等價(jià)類.在這個(gè)結(jié)構(gòu)上實(shí)現(xiàn)了初始化,判斷元素是否等價(jià)(兩個(gè)結(jié)點(diǎn)是否屬于同一個(gè)連通分量),合并等價(jià)類(連通分量)的操作. 7.34 Status TopoSeq(ALGraph G,int new )/按照題目要求給有向無環(huán)圖的結(jié)點(diǎn)重新編號(hào),并存入數(shù)組new中  int indegreeMAXSIZE; /本算法就是拓?fù)渑判?#160; FindIndegree(G,indegree);  Initstack(S);  for(i=0;i<G.vexnum;i+)    if(!indegreei) Push(S,i);  count=0;  while(!stackempty(S)      Pop(S,i);newi=+count; /把拓?fù)漤樞虼嫒霐?shù)組的對(duì)應(yīng)分量中    for(p=G.verticesi.firstarc;p;p=p->nextarc)          k=p->adjvex;      if(!(-indegreek) Push(S,k);      /while  if(count<G.vexnum) return ERROR;  return OK;/TopoSeq 7.35 int visitedMAXSIZE; void Get_Root(ALGraph G)/求有向無環(huán)圖的根,如果有的話  for(v=0;v<G.vexnum;v+)      for(w=0;w<G.vexnum;w+) visitedw=0;/每次都要將訪問數(shù)組清零    DFS(G,v); /從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷    for(flag=1,w=0;w<G.vexnum;w+)      if(!visitedw) flag=0; /如果v是根,則深度優(yōu)先遍歷可以訪問到所有結(jié)點(diǎn)    if(flag) printf("Found a root vertex:%dn",v);  /for/Get_Root,這個(gè)算法要求圖中不能有環(huán),否則會(huì)發(fā)生誤判 void DFS(ALGraph G,int v)  visitedv=1;  for(p=G.verticesv.firstarc;p;p=p->nextarc)      w=p->adjvex;    if(!visitedw) DFS(G,w);  /DFS 7.36 void Fill_MPL(ALGraph &G)/為有向無環(huán)圖G添加MPL域  FindIndegree(G,indegree);  for(i=0;i<G.vexnum;i+)    if(!indegreei) Get_MPL(G,i);/從每一個(gè)零入度頂點(diǎn)出發(fā)構(gòu)建MPL域/Fill_MPL int Get_MPL(ALGraph &G,int i)/從一個(gè)頂點(diǎn)出發(fā)構(gòu)建MPL域并返回其MPL值  if(!G.verticesi.firstarc)      G.verticesi.MPL=0;    return 0; /零出度頂點(diǎn)    else      max=0;    for(p=G.verticesi.firstarc;p;p=p->nextarc)          j=p->adjvex;      if(G.verticesj.MPL=0) k=Get_MPL(G,j);      if(k>max) max=k; /求其直接后繼頂點(diǎn)MPL的最大者        G.verticesi=max+1;/再加一,就是當(dāng)前頂點(diǎn)的MPL    return max+1;  /else/Get_MPL 7.37 int maxlen,pathMAXSIZE; /數(shù)組path用于存儲(chǔ)當(dāng)前路徑int mlpMAXSIZE; /數(shù)組mlp用于存儲(chǔ)已發(fā)現(xiàn)的最長(zhǎng)路徑 void Get_Longest_Path(ALGraph G)/求一個(gè)有向無環(huán)圖中最長(zhǎng)的路徑  maxlen=0;  FindIndegree(G,indegree);  for(i=0;i<G.vexnum;i+)      for(j=0;j<G.vexnum;j+) visitedj=0;    if(!indegreei) DFS(G,i,0);/從每一個(gè)零入度結(jié)點(diǎn)開始深度優(yōu)先遍歷    printf("Longest Path:");  for(i=0;mlpi;i+) printf("%d",mlpi); /輸出最長(zhǎng)路徑/Get_Longest_Path void DFS(ALGraph G,int i,int len)  visitedi=1;  pathlen=i;  if(len>maxlen&&!G.verticesi.firstarc) /新的最長(zhǎng)路徑      for(j=0;j<=len;j+) mlpj=pathj; /保存下來    maxlen=len;    else      for(p=G.verticesi.firstarc;p;p=p->nextarc)          j=p->adjvex;      if(!visitedj) DFS(G,j,len+1);      /else  pathi=0;  visitedi=0;/DFS 7.38 void NiBoLan_DAG(ALGraph G)/輸出有向無環(huán)圖形式表示的表達(dá)式的逆波蘭式  FindIndegree(G,indegree);  for(i=0;i<G.vexnum;i+)    if(!indegreei) r=i; /找到有向無環(huán)圖的根  PrintNiBoLan_DAG(G,i);/NiBoLan_DAG void PrintNiBoLan_DAG(ALGraph G,int i)/打印輸出以頂點(diǎn)i為根的表達(dá)式的逆波蘭式  c=G.verticesi.data;  if(!G.verticesi.firstarc) /c是原子    printf("%c",c);  else /子表達(dá)式      p=G.verticesi.firstarc;    PrintNiBoLan_DAG(G,p->adjvex);    PrintNiBoLan_DAG(G,p->nexarc->adjvex);    printf("%c",c);  /PrintNiBoLan_DAG 7.39 void PrintNiBoLan_Bitree(Bitree T)/在二叉鏈表存儲(chǔ)結(jié)構(gòu)上重做上一題  if(T->lchild) PrintNiBoLan_Bitree(T->lchild);  if(T->rchild) PrintNiBoLan_Bitree(T->rchild);  printf("%c",T->data);/PrintNiBoLan_Bitree 7.40 int Evaluate_DAG(ALGraph G)/給有向無環(huán)圖表示的表達(dá)式求值  FindIndegree(G,indegree);  for(i=0;i<G.vexnum;i+)    if(!indegreei) r=i; /找到有向無環(huán)圖的根  return Evaluate_imp(G,i);/NiBoLan_DAG int Evaluate_imp(ALGraph G,int i)/求子表達(dá)式的值  if(G.verticesi.tag=NUM) return G.verticesi.value;  else      p=G.verticesi.firstarc;    v1=Eva