《江南大学程序设计课件第七章 图》由会员分享，可在线阅读，更多相关《江南大学程序设计课件第七章 图（23页珍藏版）》请在金锄头文库上搜索。
1、第七章 图7.14Status Build_AdjList(ALGraph &G)/输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表InitALGraph(G); scanf(%d,&v);if(v0) return ERROR; /顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /边数不能为负G.arcnum=a;for(m=0;mv;m+)G.verticesm.data=getchar(); /输入各顶点的符号for(m=1;m=a;m+)t=getchar();h=getchar(); /t 为弧尾,h 为弧头if(i=Lo
2、cateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)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 上插入顶点 vif(G.vexnum+1)MAX_VERTEX_NUM return INFEASIBLE; G.vexs+G.vexnum=v;return
3、OK;/Insert_VexStatus 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_ArcStatus Delete_Vex(MGraph &G,char v)/在邻接矩阵表示的图 G 上删除顶点 vn=G.vexnu
4、m;if(m=LocateVex(G,v)0) return ERROR;G.vexsmG.vexsn; /将待删除顶点交换到最后一个顶点for(i=0;in;i+)G.arcsim=G.arcsin; G.arcsmi=G.arcsni; /将边的关系随之交换G.arcsmm.adj=0; G.vexnum-;return OK;/Delete_Vex分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.Status Delete_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图 G 上删除边(v,w)i
5、f(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/为节省篇幅,本题只给出 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)adjvex
6、=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,char v)/在十字链表表示的图 G
7、上删除顶点 vif(m=LocateVex(G,v)0) return ERROR; n=G.vexnum;for(i=0;itailvex=m) /如果待删除的边是头链上的第一个结点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/forfor(i=0;iheadvex=m) /
8、如果待删除的边是尾链上的第一个结点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/forfor(i=m;ihlink)p-headvex-; for(p=G.xlisti.firstout;p;p=p-tlink)p-tailvex-; /修改各链中的顶点序号G.vexnu
9、m-; return OK;/Delete_Vex 7.18/为节省篇幅,本题只给出 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)jvex=j) G.adjmulisti.firstedge=G.adjmulisti.firstedge-ilink; elsefor(p=G.adjmulisti.firstedge;p&p-ilink-jvex!=j
10、;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; elsefor(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.
11、arcnum-; return OK;/Delete_Arc 7.19Status Build_AdjMulist(AMLGraph &G)/输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表InitAMLGraph(G); scanf(%d,&v);if(v0) return ERROR; /顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /边数不能为负G.arcnum=a;for(m=0;mv;m+)G.adjmulistm.data=getchar(); /输入各顶点的符号for(m=1;m=a;m+)t=getchar()
12、;h=getchar(); /t 为弧尾,h 为弧头if(i=LocateVex(G,t)0) return ERROR; if(j=LocateVex(G,h)ivex=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 链表尾部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
