《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖

《《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖（46頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第七章 圖 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

2、號(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.vertices[i].firstarc=p; ????else ????{ ??????for(q=G.

3、vertices[i].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;

4、 ??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.arcs[i][j].adj) ??{ ????G.arcs[i][j].adj=1; ????G.arcnu

5、m++; ??} ??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.vexs[m]<->G.vexs[n]; //將待刪除頂點(diǎn)交換到最后一個(gè)頂點(diǎn) ??for(i=0;i

6、 ??} ??G.arcs[m][m].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.arcs[i][

7、j].adj) ??{ ????G.arcs[i][j].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=(ArcNod

8、e*)malloc(sizeof(ArcNode)); ??p->adjvex=j;p->nextarc=NULL; ??if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; ??else ??{ ????for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) ??????if(q->adjvex==j) return ERROR; //邊已經(jīng)存在 ????q->nextarc=p; ??} ??G.arcnum++; ??return OK; }//Inser

9、t_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;itailvex==m) //如果待刪除的邊是頭鏈上的第一個(gè)結(jié)點(diǎn) ????{ ??????q=G.xlist[i].f

10、irstin; ??????G.xlist[i].firstin=q->hlink; ??????free(q);G.arcnum--; ????} ????else //否則 ????{ ??????for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink); ??????if(p) ??????{ ????????q=p->hlink; ????????p->hlink=q->hlink; ????????free(q);G.arcnum--; ??????} ????}//else ??}//for

11、 ??for(i=0;iheadvex==m) //如果待刪除的邊是尾鏈上的第一個(gè)結(jié)點(diǎn) ????{ ??????q=G.xlist[i].firstout; ??????G.xlist[i].firstout=q->tlink; ??????free(q);G.arcnum--; ????} ????else //否則 ????{ ??????for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);

12、 ??????if(p) ??????{ ????????q=p->tlink; ????????p->tlink=q->tlink; ????????free(q);G.arcnum--; ??????} ????}//else ??}//for ??for(i=m;ihlink) ??????p->headvex--; ????for(p=G.xlist

13、[i].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)

14、return ERROR; ??if(G.adjmulist[i].firstedge->jvex==j) ????G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; ??else ??{ ????for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); ????if (!p) return ERROR; //未找到 ????p->ilink=p->ilink->ilink; ??} //在i鏈表中刪除該邊 ??if(G.adjmulist[

15、j].firstedge->ivex==i) ????G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink; ??else ??{ ????for(p=G.adjmulist[j].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 O

16、K; }//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

17、tchar(); //輸入各頂點(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.

18、adjmulist[i].firstedge) G.adjmulist[i].firstedge=p; ????else ????{ ??????q=G.adjmulist[i].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; //又可能

19、出現(xiàn)在邊結(jié)點(diǎn)的jvex域中 ????}//else //插入i鏈表尾部 ????if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p; ????else ????{ ??????q=G.adjmulist[i].firstedge; ??????while(q) ??????{ ????????r=q; ????????if(q->jvex==j) q=q->jlink; ????????else q=q->ilnk; ??????} ??????if(r->jvex==j) r->jlink=p; ????

20、??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

21、.arcs[y][z]&&!G.arcs[x][z]) return 0;//圖不可傳遞的條件 ??????}//if ??return 1; }//Pass_MGraph 分析:本算法的時(shí)間復(fù)雜度大概是O(n^2*d). 7.21 int Pass_ALGraph(ALGraph G)//判斷一個(gè)鄰接表存儲(chǔ)的有向圖是不是可傳遞的,是則返回1,否則返回0 { ??for(x=0;xnextarc) ????{ ??????y=p->adjvex; ?????

22、?for(q=G.vertices[y].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.vertices[m].firstarc;p;p=p->nextarc) ????if(p->adjvex=

23、=n) return 1; ??return 0; }//is_adj 7.22 int visited[MAXSIZE]; //指示頂點(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 ??{ ????visited[i]=1; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????k=p->ad

24、jvex; ??????if(!visited[k]&&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 visited[MAXSIZE]; ??InitQueue(Q); ??EnQueue(Q,i); ??while(!QueueEmpty(Q)) ??{ ????DeQu

25、eue(Q,u); ????visited[u]=1; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????k=p->adjvex; ??????if(k==j) return 1; ??????if(!visited[k]) EnQueue(Q,k); ????}//for ??}//while ??return 0; }//exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)//非遞歸遍歷強(qiáng)連通圖G { ??int visited

26、[MAXSIZE]; ??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&&!visited[j]) ??????{ ????????visit(j); ????????visited[j]=1; ????????Push(S,j); //向左走到盡頭 ??????} ??

27、??}//while ????if(!StackEmpty(S)) ????{ ??????Pop(S,j); ??????Gettop(S,i); ??????k=NextAdjVex(G,i,j); //向右走一步 ??????if(k&&!visited[k]) ??????{ ????????visit(k); ????????visited[k]=1; ????????Push(S,k); ??????} ????}//if ??}//while }//Straverse_Nonrecursive 分析:本算法的基本思想與二叉樹的先序遍歷非遞歸算法相同,

28、請(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 new[MAXSIZE],indegree[MAXSIZE]; //儲(chǔ)存結(jié)點(diǎn)的新序號(hào) ??n=G.vexnum; ??FindInDegree(G,indegree); ??InitStack(S); ??for(i=1;i

29、=0; ??while(!StackEmpty(S)) ??{ ????Pop(S,i); ????new[i]=n--; //記錄結(jié)點(diǎn)的拓?fù)淠嫘蛐蛱?hào) ????count++; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????k=p->adjvex; ??????if(!(--indegree[k])) Push(S,k); ????}//for ??}//while ??if(count

30、rintf("Old No:%d New No:%d\n",i,new[i]) ??return OK; }//TopoNo 分析:只要按拓?fù)淠嫘驅(qū)旤c(diǎn)編號(hào),就可以使鄰接矩陣成為下三角矩陣. 7.27 int visited[MAXSIZE]; 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) ??{ ????visited[i]

31、=1; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????l=p->adjvex; ??????if(!visited[l]) ????????if(exist_path_len(G,l,j,k-1)) return 1; //剩余路徑長(zhǎng)度減一 ????}//for ????visited[i]=0; //本題允許曾經(jīng)被訪問過的結(jié)點(diǎn)出現(xiàn)在另一條路徑中 ??}//else ??return 0; //沒找到 }//exist_path_len 7.28 int path[MAXSIZE],visi

32、ted[MAXSIZE]; //暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k)//求有向圖G中頂點(diǎn)u到v之間的所有簡(jiǎn)單路徑,k表示當(dāng)前路徑長(zhǎng)度 { ??path[k]=u; //加入當(dāng)前路徑中 ??visited[u]=1; ??if(u==v) //找到了一條簡(jiǎn)單路徑 ??{ ????printf("Found one path!\n"); ????for(i=0;path[i];i++) printf("%d",path[i]); //打印輸出 ??} ??else ????for(p=G.vert

33、ices[u].firstarc;p;p=p->nextarc) ????{ ??????l=p->adjvex; ??????if(!visited[l]) Find_All_Path(G,l,v,k+1); //繼續(xù)尋找 ????} ??visited[u]=0; ??path[k]=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

34、,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ù) ????visited[i]=1; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????l=p->adjvex; ??????if(!visited[l]) ????????sum+=GetPathNum_L

35、en(G,l,j,len-1)//剩余路徑長(zhǎng)度減一 ????}//for ????visited[i]=0; //本題允許曾經(jīng)被訪問過的結(jié)點(diǎn)出現(xiàn)在另一條路徑中 ??}//else ??return sum; }//GetPathNum_Len 7.30 int visited[MAXSIZE]; int path[MAXSIZE]; //暫存當(dāng)前路徑 int cycles[MAXSIZE][MAXSIZE]; //儲(chǔ)存發(fā)現(xiàn)的回路所包含的結(jié)點(diǎn) int thiscycle[MAXSIZE]; //儲(chǔ)存當(dāng)前發(fā)現(xiàn)的一個(gè)回路 int cycount=0; //已發(fā)現(xiàn)的回路個(gè)數(shù)

36、 void GetAllCycle(ALGraph G)//求有向圖中所有的簡(jiǎn)單回路 { ??for(v=0;v

37、p=p->nextarc) ??{ ????w=p->adjvex; ????if(!visited[w]) DFS(G,w,k+1); ????else //發(fā)現(xiàn)了一條回路 ????{ ??????for(i=0;path[i]!=w;i++); //找到回路的起點(diǎn) ??????for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把回路復(fù)制下來 ??????if(!exist_cycle()) cycles[cycount++]=thiscycle;//如果該回路尚未被記錄過,就添加到記錄中 ??????for(i=0;i

38、exnum;i++) thiscycle[i]=0; //清空目前回路數(shù)組 ????}//else ??}//for ??path[k]=0; ??visited[k]=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 temp[MAXSIZE]; ??for(i=0;i

39、是,所有結(jié)點(diǎn)和它們的順序都相同 ????j=0;c=thiscycle�; //例如,142857和857142是相同的回路 ????for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);//在cycles的一個(gè)行向量中尋找等于thiscycle第一個(gè)結(jié)點(diǎn)的元素 ????if(cycles[i][k]) //有與之相同的一個(gè)元素 ????{ ??????for(m=0;cycles[i][k+m];m++) ????????temp[m]=cycles[i][k+m]; ??????for(n=0;n

40、???temp[m]=cycles[i][n]; //調(diào)整cycles中的當(dāng)前記錄的循環(huán)相位并放入temp數(shù)組中 ??????if(!StrCompare(temp,thiscycle)) //與thiscycle比較 ????????return 1; //完全相等 ??????for(m=0;m

41、明存在一條回路;掃描路徑向量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中得到1428

42、57,與thiscycle比較,發(fā)現(xiàn)相同,因此142857和857142是同一條回路,不予存儲(chǔ).這個(gè)算法太復(fù)雜,很難保證細(xì)節(jié)的準(zhǔn)確性,大家理解思路便可.希望有人給出更加簡(jiǎn)捷的算法. 7.31 int visited[MAXSIZE]; int finished[MAXSIZE]; 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

43、0; ??for(v=0;v=0;i--) //第二次逆向的深度優(yōu)先遍歷 ??{ ????v=finished(i); ????if(!visited[v]) ????{ ??????printf("\n"); //不同的強(qiáng)連通分量在不同的行輸出 ??????DFS2(G,v); ???

44、?} ??}//for }//Get_SGraph void DFS1(OLGraph G,int v)//第一次深度優(yōu)先遍歷的算法 { ??visited[v]=1; ??for(p=G.xlist[v].firstout;p;p=p->tlink) ??{ ????w=p->headvex; ????if(!visited[w]) DFS1(G,w); ??}//for ??finished[++count]=v; //在第一次遍歷中建立finished數(shù)組 }//DFS1 void DFS2(OLGraph G,int v)//第二次逆向的深度優(yōu)先遍歷的算法

45、 { ??visited[v]=1; ??printf("%d",v); //在第二次遍歷中輸出結(jié)點(diǎn)序號(hào) ??for(p=G.xlist[v].firstin;p;p=p->hlink) ??{ ????w=p->tailvex; ????if(!visited[w]) 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,用孩

46、子兄弟鏈表存儲(chǔ) { ??for(j=0;jnextarc) ????????if(p->adjvex==k) closedge[j].lowcost=p->cost; ????}//if ??closedge[k].lowcost=0; ??for(i=1;i

47、(closedge); ????if(closedge[k].lowcostnextarc) ????????if(p->costadjvex].lowcost) ??????????closedge[p->adjvex]={k,p->cost}; ????}//if

48、 ????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(CS

49、TNode)); ????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è)孩

50、子的兄弟 ??} }//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(n^2). 7.33 typedef struct { ?????? ?????????? int vex; //結(jié)點(diǎn)序號(hào) ?? ?????????????? int ecno

51、; //結(jié)點(diǎn)所屬的連通分量號(hào) ?? ???????????? } VexInfo; VexInfo vexs[MAXSIZE]; //記錄結(jié)點(diǎn)所屬連通分量號(hào)的數(shù)組 void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化 { ??for(i=0;i

52、(vexs[i].ecno==vexs[j].ecno) return 1; ??else return 0; }//is_ec void merge_ec(VexInfo &vexs[ ],int ec1,int ec2)//合并連通分量ec1和ec2 { ??for(i=0;vexs[i].vex;i++) ????if(vexs[i].ecno==ec2) vexs[i].ecno==ec1; }//merge_ec void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T)//求圖的最小生成樹的克

53、魯斯卡爾算法 { ??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,vexs[u].ecno,vexs[v].ecno); //合并連通分量 ??????ecnum--; ????} ??

54、??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è)孩子

55、??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),

56、并存入數(shù)組new中 { ??int indegree[MAXSIZE]; //本算法就是拓?fù)渑判? ??FindIndegree(G,indegree); ??Initstack(S); ??for(i=0;inextarc) ??

57、??{ ??????k=p->adjvex; ??????if(!(--indegree[k])) Push(S,k); ????} ??}//while ??if(count

58、要將訪問數(shù)組清零 ????DFS(G,v); //從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷 ????for(flag=1,w=0;w

59、firstarc;p;p=p->nextarc) ??{ ????w=p->adjvex; ????if(!visited[w]) DFS(G,w); ??} }//DFS 7.36 void Fill_MPL(ALGraph &G)//為有向無環(huán)圖G添加MPL域 { ??FindIndegree(G,indegree); ??for(i=0;i

60、//從一個(gè)頂點(diǎn)出發(fā)構(gòu)建MPL域并返回其MPL值 { ??if(!G.vertices[i].firstarc) ??{ ????G.vertices[i].MPL=0; ????return 0; //零出度頂點(diǎn) ??} ??else ??{ ????max=0; ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????j=p->adjvex; ??????if(G.vertices[j].MPL==0) k=Get_MPL(G,j); ??????if(k>max) max=k; //求其直接后繼頂

61、點(diǎn)MPL的最大者 ????} ????G.vertices[i]=max+1;//再加一,就是當(dāng)前頂點(diǎn)的MPL ????return max+1; ??}//else }//Get_MPL 7.37 int maxlen,path[MAXSIZE]; //數(shù)組path用于存儲(chǔ)當(dāng)前路徑 int mlp[MAXSIZE]; //數(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<

62、G.vexnum;i++) ??{ ????for(j=0;j

63、len>maxlen&&!G.vertices[i].firstarc) //新的最長(zhǎng)路徑 ??{ ????for(j=0;j<=len;j++) mlp[j]=path[j]; //保存下來 ????maxlen=len; ??} ??else ??{ ????for(p=G.vertices[i].firstarc;p;p=p->nextarc) ????{ ??????j=p->adjvex; ??????if(!visited[j]) DFS(G,j,len+1); ????} ??}//else ??path[i]=0; ??visited[i]=0;

64、}//DFS 7.38 void NiBoLan_DAG(ALGraph G)//輸出有向無環(huán)圖形式表示的表達(dá)式的逆波蘭式 { ??FindIndegree(G,indegree); ??for(i=0;i

65、f(!G.vertices[i].firstarc) //c是原子 ????printf("%c",c); ??else //子表達(dá)式 ??{ ????p=G.vertices[i].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)上重做上一題 { ??

66、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