《清华大学数据结构7》由会员分享，可在线阅读，更多相关《清华大学数据结构7（31页珍藏版）》请在金锄头文库上搜索。
1、清华大学数据结构清华大学数据结构 7 7第七章 图7.14 Status Build_AdjList(ALGraph scanf(“%d“,if(vnextarc;q=q-nextarc);q-nextarc=p;p-adjvex=j;p-nextarc=NULL;/whilereturn OK;/Build_AdjList 7.15 /本题中的图 G 均为有向无权图,其余情况容易由此写出Status Insert_Vex(MGraph G.vexs+G.vexnum=v;return OK;/Insert_Vex Status Insert_Arc(MGraph /将待删除顶点交换到最后一个
2、顶点for(i=0;iadjvex=j;p-nextarc=NULL;if(!G.verticesi.firstarc) G.verticesi.firstarc=p;elsefor(q=G.verticesi.firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex=j) return ERROR; /边已经存在q-nextarc=p;G.arcnum+;return OK;/Insert_Arc 7.17 /为节省篇幅,本题只给出较为复杂的 Delete_Vex 算法.其余算法请自行写出. Status Delete_Vex(OLGraph G.xlisti
3、.firstin=q-hlink;free(q);G.arcnum-;else /否则for(p=G.xlisti.firstin;pp=p-hlink);if(p)q=p-hlink;p-hlink=q-hlink;free(q);G.arcnum-;/else/forfor(i=0;iheadvex=m) /如果待删除的边是尾链上的第一个结点q=G.xlisti.firstout;G.xlisti.firstout=q-tlink;free(q);G.arcnum-;else /否则for(p=G.xlisti.firstout;pp=p-tlink);if(p)q=p-tlink;p-t
4、link=q-tlink;free(q);G.arcnum-;/else/forfor(i=m;ihlink)p-headvex-;for(p=G.xlisti.firstout;p;p=p-tlink)p-tailvex-; /修改各链中的顶点序号G.vexnum-;return OK;/Delete_Vex 7.18 /为节省篇幅,本题只给出 Delete_Arc 算法.其余算法请自行写出. Status Delete_Arc(AMLGraph elsefor(p=G.adjmulisti.firstedge;pp=p-ilink);if (!p) return ERROR; /未找到p-
5、ilink=p-ilink-ilink; /在 i 链表中删除该边if(G.adjmulistj.firstedge-ivex=i)G.adjmulistj.firstedge=G.adjmulistj.firstedge-jlink;elsefor(p=G.adjmulistj.firstedge;pp=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(AMLG
6、raph scanf(“%d“,if(vivex=i;p-jvex=j;p-ilink=NULL;p-jlink=NULL; /边结点赋初值if(!G.adjmulisti.firstedge) G.adjmulisti.firstedge=p;elseq=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 值既可能出现在边结点的 ivex 域中,else r-jlink=p; /又可能出现在边结点的 jvex 域中/else /插入 i 链表
7、尾部if(!G.adjmulistj.firstedge) G.adjmulistj.firstedge=p;elseq=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 链表尾部/forreturn OK;/Build_AdjList 7.20 int Pass_MGraph(MGraph G)/判断一个邻接矩阵存储的有向图是不是可传递的,是则返回 1,否则返回 0for(x=0;xnextarc)y
8、=p-adjvex;for(q=G.verticesy.firstarc;q;q=q-nextarc)z=q-adjvex;if(z!=x/for/for/Pass_ALGraph int is_adj(ALGraph G,int m,int n)/判断有向图 G 中是否存在边(m,n),是则返回 1,否则返回 0for(p=G.verticesm.firstarc;p;p=p-nextarc)if(p-adjvex=n) return 1;return 0;/is_adj 7.22 int visitedMAXSIZE; /指示顶点是否在当前路径上 int exist_path_DFS(AL
9、Graph G,int i,int j)/深度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0if(i=j) return 1; /i 就是 jelsevisitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!visitedk/i 下游的顶点到 j 有路径/for/else/exist_path_DFS 7.23 int exist_path_BFS(ALGraph G,int i,int j)/广度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0in
10、t 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/whilereturn 0;/exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)/非递归遍历强连通图 Gint visitedMAXSIZE;InitStack(
11、S);Push(S,GetVex(S,1); /将第一个顶点入栈visit(1);visited =1;while(!StackEmpty(S)while(Gettop(S,i)if(jvisitedj=1;Push(S,j); /向左走到尽头/whileif(!StackEmpty(S)Pop(S,j);Gettop(S,i);k=NextAdjVex(G,i,j); /向右走一步if(kvisitedk=1;Push(S,k);/if/while/Straverse_Nonrecursive分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考 6.37.由于是强连通图,所以从第一
12、个结点出发一定能够访问到所有结点. 7.25 见书后解答. 7.26 Status TopoNo(ALGraph G)/按照题目要求顺序重排有向图中的顶点int newMAXSIZE,indegreeMAXSIZE; /储存结点的新序号n=G.vexnum;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);/for/whileif(count0)visitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-ad
13、jvex;if(!visitedl)if(exist_path_len(G,l,j,k-1) return 1; /剩余路径长度减一/forvisitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中/elsereturn 0; /没找到/exist_path_len 7.28 int pathMAXSIZE,visitedMAXSIZE; /暂存遍历过程中的路径 int Find_All_Path(ALGraph G,int u,int v,int k)/求有向图 G中顶点 u 到 v 之间的所有简单路径,k 表示当前路径长度pathk=u; /加入当前路径中visitedu=1;
14、if(u=v) /找到了一条简单路径printf(“Found one path!n“);for(i=0;pathi;i+) printf(“%d“,pathi); /打印输出elsefor(p=G.verticesu.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl) Find_All_Path(G,l,v,k+1); /继续寻找visitedu=0;pathk=0; /回溯/Find_All_Path main().Find_All_Path(G,u,v,0); /在主函数中初次调用,k 值应为 0./main 7.29 int GetPathN
15、um_Len(ALGraph G,int i,int j,int len)/求邻接表方式存储的有向图 G 的顶点 i 到 j 之间长度为 len 的简单路径条数if(i=j /找到了一条路径,且长度符合要求else if(len0)sum=0; /sum 表示通过本结点的路径数visitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)sum+=GetPathNum_Len(G,l,j,len-1)/剩余路径长度减一/forvisitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中/elsereturn sum;/GetPathNum_Len 7.30 int visitedMAXSIZE;int pathMAXSIZE; /暂存当前路径int cyclesMAXSIZEMAXSIZE; /储存发
