《數(shù)據(jù)結構題集》答案 第7章 圖
《《數(shù)據(jù)結構題集》答案 第7章 圖》由會員分享，可在線閱讀，更多相關《《數(shù)據(jù)結構題集》答案 第7章 圖（46頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第七章 圖
7.14
Status Build_AdjList(ALGraph &G)//輸入有向圖的頂點數(shù),邊數(shù),頂點信息和邊的信息建立鄰接表
{
??InitALGraph(G);
??scanf("%d",&v);
??if(v<0) return ERROR; //頂點數(shù)不能為負
??G.vexnum=v;
??scanf("%d",&a);
??if(a<0) return ERROR; //邊數(shù)不能為負
??G.arcnum=a;
??for(m=0;m 2、號
??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; //頂點未找到
????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均為有向無權圖,其余情況容易由此寫出
Status Insert_Vex(MGraph &G, char v)//在鄰接矩陣表示的圖G上插入頂點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上刪除頂點v
{
??n=G.vexnum;
??if((m=LocateVex(G,v))<0) return ERROR;
??G.vexs[m]<->G.vexs[n]; //將待刪除頂點交換到最后一個頂點
??for(i=0;i 6、
??}
??G.arcs[m][m].adj=0;
??G.vexnum--;
??return OK;
}//Delete_Vex
分析:如果不把待刪除頂點交換到最后一個頂點的話,算法將會比較復雜,而伴隨著大量元素的移動,時間復雜度也會大大增加.
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算法.其余算法請自行寫出.
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é)省篇幅,本題只給出較為復雜的Delete_Vex算法.其余算法請自行寫出.
Status Delete_Vex(OLGraph &G,char v)//在十字鏈表表示的圖G上刪除頂點v
{
??if((m=LocateVex(G,v))<0) return ERROR;
??n=G.vexnum;
??for(i=0;i 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;i 12、
??????if(p)
??????{
????????q=p->tlink;
????????p->tlink=q->tlink;
????????free(q);G.arcnum--;
??????}
????}//else
??}//for
??for(i=m;i 13、[i].firstout;p;p=p->tlink)
??????p->tailvex--; //修改各鏈中的頂點序號
??}
??G.vexnum--;
??return OK;
}//Delete_Vex
7.18
//為節(jié)省篇幅,本題只給出Delete_Arc算法.其余算法請自行寫出.
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)//輸入有向圖的頂點數(shù),邊數(shù),頂點信息和邊的信息建立鄰接多重表
{
??InitAMLGraph(G);
??scanf("%d",&v);
??if(v<0) return ERROR; //頂點數(shù)不能為負
??G.vexnum=v;
??scanf(%d",&a);
??if(a<0) return ERROR; //邊數(shù)不能為負
??G.arcnum=a;
??for(m=0;m 17、tchar(); //輸入各頂點的符號
??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; //頂點未找到
????p=(EBox*)malloc(sizeof(EBox));
????p->ivex=i;p->jvex=j;
????p->ilink=NULL;p->jlink=NULL; //邊結點賦初值
????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)在邊結點的ivex域中,
??????else r->jlink=p; //又可能 19、出現(xià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)//判斷一個鄰接矩陣存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
??for(x=0;x 21、.arcs[y][z]&&!G.arcs[x][z]) return 0;//圖不可傳遞的條件
??????}//if
??return 1;
}//Pass_MGraph
分析:本算法的時間復雜度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判斷一個鄰接表存儲的有向圖是不是可傳遞的,是則返回1,否則返回0
{
??for(x=0;x 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]; //指示頂點是否在當前路徑上
int exist_path_DFS(ALGraph G,int i,int j)//深度優(yōu)先判斷有向圖G中頂點i到頂點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下游的頂點到j有路徑
????}//for
??}//else
}//exist_path_DFS
7.23
int exist_path_BFS(ALGraph G,int i,int j)//廣度優(yōu)先判斷有向圖G中頂點i到頂點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)//非遞歸遍歷強連通圖G
{
??int visited 26、[MAXSIZE];
??InitStack(S);
??Push(S,GetVex(S,1)); //將第一個頂點入棧
??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、請參考6.37.由于是強連通圖,所以從第一個結點出發(fā)一定能夠訪問到所有結點.
7.25
見書后解答.
7.26
Status TopoNo(ALGraph G)//按照題目要求順序重排有向圖中的頂點
{
??int new[MAXSIZE],indegree[MAXSIZE]; //儲存結點的新序號
??n=G.vexnum;
??FindInDegree(G,indegree);
??InitStack(S);
??for(i=1;i 29、=0;
??while(!StackEmpty(S))
??{
????Pop(S,i);
????new[i]=n--; //記錄結點的拓撲逆序序號
????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
分析:只要按拓撲逆序對頂點編號,就可以使鄰接矩陣成為下三角矩陣.
7.27
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑
{
??if(i==j&&k==0) return 1; //找到了一條路徑,且長度符合要求
??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; //剩余路徑長度減一
????}//for
????visited[i]=0; //本題允許曾經(jīng)被訪問過的結點出現(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中頂點u到v之間的所有簡單路徑,k表示當前路徑長度
{
??path[k]=u; //加入當前路徑中
??visited[u]=1;
??if(u==v) //找到了一條簡單路徑
??{
????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值應為0
??...
}//main
7.29
int GetPathNum_Len(ALGraph G,int i 34、,int j,int len)//求鄰接表方式存儲的有向圖G的頂點i到j之間長度為len的簡單路徑條數(shù)
{
??if(i==j&&len==0) return 1; //找到了一條路徑,且長度符合要求
??else if(len>0)
??{
????sum=0; //sum表示通過本結點的路徑數(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)//剩余路徑長度減一
????}//for
????visited[i]=0; //本題允許曾經(jīng)被訪問過的結點出現(xiàn)在另一條路徑中
??}//else
??return sum;
}//GetPathNum_Len
7.30
int visited[MAXSIZE];
int path[MAXSIZE]; //暫存當前路徑
int cycles[MAXSIZE][MAXSIZE]; //儲存發(fā)現(xiàn)的回路所包含的結點
int thiscycle[MAXSIZE]; //儲存當前發(fā)現(xiàn)的一個回路
int cycount=0; //已發(fā)現(xiàn)的回路個數(shù) 36、
void GetAllCycle(ALGraph G)//求有向圖中所有的簡單回路
{
??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++); //找到回路的起點
??????for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把回路復制下來
??????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; //注意只有當前路徑上的結點visited為真.因此一旦遍歷中發(fā)現(xiàn)當前結點visited為真,即表示發(fā)現(xiàn)了一條回路
}//DFS
int exist_cycle()//判斷thiscycle數(shù)組中記錄的回路在cycles的記錄中是否已經(jīng)存在
{
??int temp[MAXSIZE];
??for(i=0;i 39、是,所有結點和它們的順序都相同
????j=0;c=thiscycle�; //例如,142857和857142是相同的回路
????for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);//在cycles的一個行向量中尋找等于thiscycle第一個結點的元素
????if(cycles[i][k]) //有與之相同的一個元素
????{
??????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中的當前記錄的循環(huán)相位并放入temp數(shù)組中
??????if(!StrCompare(temp,thiscycle)) //與thiscycle比較
????????return 1; //完全相等
??????for(m=0;m 41、明存在一條回路;掃描路徑向量path可以獲得這條回路上的所有結點.把結點序列(例如,142857)存入thiscycle中;由于這種算法中,一條回路會被發(fā)現(xiàn)好幾次,所以必須先判斷該回路是否已經(jīng)在cycles中被記錄過,如果沒有才能存入cycles的一個行向量中.把cycles的每一個行向量取出來與之比較.由于一條回路可能有多種存儲順序,比如142857等同于285714和571428,所以還要調(diào)整行向量的次序,并存入temp數(shù)組,例如,thiscycle為142857第一個結點為1,cycles的當前向量為857142,則找到后者中的1,把1后部分提到1前部分前面,最終在temp中得到1428 42、57,與thiscycle比較,發(fā)現(xiàn)相同,因此142857和857142是同一條回路,不予存儲.這個算法太復雜,很難保證細節(jié)的準確性,大家理解思路便可.希望有人給出更加簡捷的算法.
7.31
int visited[MAXSIZE];
int finished[MAXSIZE];
int count; //count在第一次深度優(yōu)先遍歷中用于指示finished數(shù)組的填充位置
void Get_SGraph(OLGraph G)//求十字鏈表結構儲存的有向圖G的強連通分量
{
??count=0;
??for(v=0;v 43、0;
??for(v=0;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); //在第二次遍歷中輸出結點序號
??for(p=G.xlist[v].firstin;p;p=p->hlink)
??{
????w=p->tailvex;
????if(!visited[w]) DFS2(G,w);
??}//for
}//DFS2
分析:求有向圖的強連通分量的算法的時間復雜度和深度優(yōu)先遍歷相同,也為O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//從頂點k出發(fā),構造鄰接表結構的有向圖G的最小生成森林T,用孩 46、子兄弟鏈表存儲
{
??for(j=0;j 47、(closedge);
????if(closedge[k].lowcost 48、
????else Forest_Prim(G,k); //對另外一個連通分量執(zhí)行算法
??}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把邊(i,j)添加到孩子兄弟鏈表表示的樹T中
{
??p=Locate(T,i); //找到結點i對應的指針p,過程略
??q=(CSTNode*)malloc(sizeof(CSTNode));
??q->data=j;
??if(!p) //起始頂點不屬于森林中已有的任何一棵樹
??{
????p=(CSTNode*)malloc(sizeof(CS 49、TNode));
????p->data=i;
????for(r=T;r->nextsib;r=r->nextsib);
????r->nextsib=p;
????p->firstchild=q;
??} //作為新樹插入到最右側
??else if(!p->firstchild) //雙親還沒有孩子
????p->firstchild=q; //作為雙親的第一個孩子
??else //雙親已經(jīng)有了孩子
??{
????for(r=p->firstchild;r->nextsib;r=r->nextsib);
????r->nextsib=q; //作為雙親最后一個孩 50、子的兄弟
??}
}//Addto_Forest
main()
{
??...
??T=(CSTNode*)malloc(sizeof(CSTNode)); //建立樹根
??T->data=1;
??Forest_Prim(G,1,T);
??...
}//main
分析:這個算法是在Prim算法的基礎上添加了非連通圖支持和孩子兄弟鏈表構建模塊而得到的,其時間復雜度為O(n^2).
7.33
typedef struct {
?????? ?????????? int vex; //結點序號
?? ?????????????? int ecno 51、; //結點所屬的連通分量號
?? ???????????? } VexInfo;
VexInfo vexs[MAXSIZE]; //記錄結點所屬連通分量號的數(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; //連通分量個數(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); //找到結點i對應的指針p,過程略
??q=(CSTNode*)malloc(sizeof(CSTNode));
??q->data=j;
??if(!p->firstchild) //雙親還沒有孩子
????p->firstchild=q; //作為雙親的第一個孩子
55、??else //雙親已經(jīng)有了孩子
??{
????for(r=p->firstchild;r->nextsib;r=r->nextsib);
????r->nextsib=q; //作為雙親最后一個孩子的兄弟
??}
}//Addto_CSTree
分析:本算法使用一維結構體變量數(shù)組來表示等價類,每個連通分量所包含的所有結點屬于一個等價類.在這個結構上實現(xiàn)了初始化,判斷元素是否等價(兩個結點是否屬于同一個連通分量),合并等價類(連通分量)的操作.
7.34
Status TopoSeq(ALGraph G,int new[ ])//按照題目要求給有向無環(huán)圖的結點重新編號, 56、并存入數(shù)組new中
{
??int indegree[MAXSIZE]; //本算法就是拓撲排序
??FindIndegree(G,indegree);
??Initstack(S);
??for(i=0;i 57、??{
??????k=p->adjvex;
??????if(!(--indegree[k])) Push(S,k);
????}
??}//while
??if(count 58、要將訪問數(shù)組清零
????DFS(G,v); //從頂點v出發(fā)進行深度優(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、//從一個頂點出發(fā)構建MPL域并返回其MPL值
{
??if(!G.vertices[i].firstarc)
??{
????G.vertices[i].MPL=0;
????return 0; //零出度頂點
??}
??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、點MPL的最大者
????}
????G.vertices[i]=max+1;//再加一,就是當前頂點的MPL
????return max+1;
??}//else
}//Get_MPL
7.37
int maxlen,path[MAXSIZE]; //數(shù)組path用于存儲當前路徑
int mlp[MAXSIZE]; //數(shù)組mlp用于存儲已發(fā)現(xiàn)的最長路徑
void Get_Longest_Path(ALGraph G)//求一個有向無環(huán)圖中最長的路徑
{
??maxlen=0;
??FindIndegree(G,indegree);
??for(i=0;i< 62、G.vexnum;i++)
??{
????for(j=0;j 63、len>maxlen&&!G.vertices[i].firstarc) //新的最長路徑
??{
????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)圖形式表示的表達式的逆波蘭式
{
??FindIndegree(G,indegree);
??for(i=0;i 65、f(!G.vertices[i].firstarc) //c是原子
????printf("%c",c);
??else //子表達式
??{
????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)//在二叉鏈表存儲結構上重做上一題
{
?? 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)圖表示的表達式求值
{
??FindIndegree(G,indegree);
??for(i=0;i
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 6.煤礦安全生產(chǎn)科普知識競賽題含答案
- 2.煤礦爆破工技能鑒定試題含答案
- 3.爆破工培訓考試試題含答案
- 2.煤礦安全監(jiān)察人員模擬考試題庫試卷含答案
- 3.金屬非金屬礦山安全管理人員（地下礦山）安全生產(chǎn)模擬考試題庫試卷含答案
- 4.煤礦特種作業(yè)人員井下電鉗工模擬考試題庫試卷含答案
- 1 煤礦安全生產(chǎn)及管理知識測試題庫及答案
- 2 各種煤礦安全考試試題含答案
- 1 煤礦安全檢查考試題
- 1 井下放炮員練習題含答案
- 2煤礦安全監(jiān)測工種技術比武題庫含解析
- 1 礦山應急救援安全知識競賽試題
- 1 礦井泵工考試練習題含答案
- 2煤礦爆破工考試復習題含答案
- 1 各種煤礦安全考試試題含答案
