东北大学：《数据结构》课程教学资源（学习资料）第七章 图

第七章图 7.14 Status Build AdjList( ALGraph&G输入有向图的顶点数边数顶点信息和边的 信息建立邻接表 InitAL Graph(G); nf("%d", &v); fyvnextarc; q=q->nextarc); q->nextare-p; p->adjvex=i p->nextarc=NULL i//while eturn OK i//Build AdjList 7.15 ∥本题中的图G均为有向无权图,其余情况容易由此写出 Status Insert vex( MGraph&G, char v/在邻接矩阵表示的图G上插入顶点ⅴ If(G. vexnum+lPMAX VERTEX NUM return INFEASIBLE, G vex++G. vexnum=v eturn oK g//nsert Vex

第七章 图 7.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的 信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(vnextarc;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; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert Arc( MGraph&G, char v, char w∥在邻接矩阵表示的图G上插入边 if(LOcate Vex(G, v)0)return ERROR; if(=Locate Vex(G, w) G vex[n],/将待删除顶点交换到最后一个顶点 for(F0; i<n; i++) G arcs[m=G arcs[n]: G. arcs][= G arcs[;∥将边的关系随之交换 Garcs m). adF0 G. vexnun return OK i/Delete Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂而伴随 着大量元素的移动时间复杂度也会大大增加 Status delete arc( MGraph&G, char v, char w/在邻接矩阵表示的图G上删除边 (v,w) If(( Locate Vex(G, v)o) return ERROR, if(LOcate Vex(G, w)0)return ERROR; if(G arcs[O0adj) G arcs[]adj=0; G. arcnum-- return OK i//Delete Arc 7.16

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图 G 上插入边 (v,w) { if((i=LocateVex(G,v))G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i<n;i++) { G.arcs[i][m]=G.arcs[i][n]; G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 } 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][j].adj) { G.arcs[i][j].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(LOcate Vex(G, v))adjvex=j, p->nextarc=NULL if(!G vertices[i]. firstarc)Gvertices[i]. firstarc=p else for(q=Gvertices[]. firstarc: q->q->nextarc q=q->nextarc) fq→> adnex=j) return error;∥边已经存在 q->nextarc=p; G arcum++. eturn oK 3//nsert Arc 7.17 ∥.节省篇幅,本题只给出较为复杂的 Delete vex算法.其余算法请自行写出 Status Delete Vex( OGRaph& G. char v∥在十字链表表示的图G上删除顶点v if((m=Locate Vex(G, v)0) return ERROR; n=G. vexnum for(i=0in;计+)/删除所有以v为头的边 if(G xlist[] firstin-> tailvex==m)∥如果待删除的边是头链上的第一个结点 FG. xlist]. firstin G xlist[ firstin=q->hlink free(q); Garcum else/否则 for(p=Gxlist[]. firstin p&&p-hlink->tailvexl=m p=p-hlink) qFE p->hlink=q->hlink free(q): G.arcnum-; i/else

//为节省篇幅,本题只给出 Insert_Arc 算法.其余算法请自行写出. Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))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; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc 7.17 //为节省篇幅,本题只给出较为复杂的 Delete_Vex 算法.其余算法请自行写出. Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图 G 上删除顶点 v { if((m=LocateVex(G,v))tailvex==m) //如果待删除的边是头链上的第一个结点 { q=G.xlist[i].firstin; 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

i//for for(i=0in;i+)/删除所有以v为尾的边 if(G xlist [].firstout> headvex=m)∥/如果待删除的边是尾链上的第一个结点 FG. xlist[]. firstout G xlist[]. firstout=q->tlink free(q): G else∥则 for(p=G xlist i firstout: p&&p->tIink->headvexl=m P=p->tlink); q=p->tlink p→ tlink=q> tlink free(q): G.arcnum-- i/else for(i=mihlink p->head vex-, for(p=G xlist [i]. firstout p: p=p->tlink) tailvex-;∥修改各链中的顶点序号 G.vexnum-- return OK i/Delete Vex 7.18 ∥.节省篇幅,本题只给出 Delete arc算法.其余算法请自行写出. Status delete arc( AMLGraph& G. char v, char w)∥在邻接多重表表示的图G上删 除边(v if((i-Locate Vex(G, v)0) return ERROR if(=Locate Vex(G, w)0) return ERROR; if(G. adjmulist[j]. firstedge- G. adjmulist[i].firstedge=G. adjmulist[]. firsted ge->ilink; el

}//for for(i=0;iheadvex==m) //如果待删除的边是尾链上的第一个结点 { 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); 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[i].firstout;p;p=p->tlink) p->tailvex--; //修改各链中的顶点序号 } G.vexnum--; 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))jvex==j) G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else {

for(p=G. adjmulist[]. firstedge p&&p->ilink->jvex!=j p=p->ilink ) if(p) return error;∥.找到 p->link=p->ilink->ilink }/在i链表中删除该边 if(G. adjmulist []. firstedge->ivex==i) G. adjmulist[]. firstedge=G. adjmulist[]. firstedge->jlink else for(p=G. adjmulist I]. firsted ge, p&&p->jlink->ivex=i; p=p->jlink ); if(p) return error;∥未找到 q=p->jlink; p->jlink=q->jlin ee }/在i链表中删除该边 G.arcum- eturn OK. i/Delete Arc 7.19 Status Build Ad](( AMLGraph&G输入有向图的顶点数边数顶点信息和 边的信息建立邻接多重表 Init AMLGraph(G); scanf("%d", &v) ifvlvex=lp→ pve=J p> ilink-NULL p>jink=NULL;∥边结点赋初值 if(!G. adjmulist [ ].firstedge)G. adjmulist [].firstedge=p: else q=G.adjmulist i firsted ge, while(q)

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[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 OK; }//Delete_Arc 7.19 Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和 边的信息建立邻接多重表 { InitAMLGraph(G); scanf("%d",&v); if(vivex=i;p->jvex=j; p->ilink=NULL;p->jlink=NULL; //边结点赋初值 if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p; else { q=G.adjmulist[i].firstedge; while(q)

, if(q->ivex==1)q=q->ilink else q=q->jlink; if(r->ivex=i)r->lik=pJ/注意i值既可能出现在边结点的ivex域中, else r-> blink=p;∥又可能出现在边结点的jvex域中 }/else/插入i链表尾部 if(!G ad]mulit [ ] firstedge)G. adjmulist[].firstedge=p; else q=G. adjmulist i firsted ge, while(q) q if(q->jvexDq=q->jlink; else q=q->ink; if(r->jex=D)r->jlink=p else r->ilink=p lele/插入j链表尾部 i//for eturn oK 3//Build AdjList 720 int Pass MGraph( MGraph g判断一个邻接矩阵存储的有向图是不是可传递的, 是则返回1,否则返回0 for(x=0; X<G. vexnum; x++) for(y=0; y<G. vexnum; y++) if(G arcs]yD for(z=0; Z<G. vexnum; Z++) if(zl=x&& G arcs[z]&& G arcs][z]) return0/图不可传递的条件 i/if eturn i//Pass MGraph 分析:本算法的时间复杂度大概是O(n^2*d) 721 int Pass ALGraph( ALGraph G判断一个邻接表存储的有向图是不是可传递的, 是则返回1,否则返回0

{ 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.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; else r->ilink=p; }//else //插入 j 链表尾部 }//for return OK; }//Build_AdjList 7.20 int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的, 是则返回 1,否则返回 0 { for(x=0;x<G.vexnum;x++) for(y=0;y<G.vexnum;y++) if(G.arcs[x][y]) { for(z=0;z<G.vexnum;z++) if(z!=x&&G.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; Xnextarc) y=p->adjvex for(q=G vertices ]. firstarc; q: q=q->nextarc) if(zl=x&&! is adj(G, x, z)) return 0; i//for i//Pass ALGraph int is adj( ALGraph C, int m, int ny/判断有向图G中是否存在边(mn),是则返回1, 否则返回0 for(p=G vertices(m). firstarc p: p=p->nextarc) if(p->adjvex--n) return 1 return 0 i//is adj 722 int visited MAXSIZE]∥指示顶点是否在当前路径上 int exist_ path DFS( ALGraph G, int i, int j)∥/深度优先判断有向图G中顶点i到顶点 j是否有路径是则返回1,否则返回0 ifi=j) return1;∥就是 visited [F=1 for(p=G vertices ]. firstarc, p: p=p->nextarc) k=p->adjvex if(!visited [k]&& exist_path(kj) return 1/下游的顶点到j有路径 i//else i//exist path DFS 7.23 int exist path BFS( ALGraph g,nti,itj)∥广度优先判断有向图G中顶点i到顶点 j是否有路径,是则返回1,否则返回0

{ for(x=0;xnextarc) { y=p->adjvex; 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==n) return 1; return 0; }//is_adj 7.22 int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图 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->adjvex; 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)//广度优先判断有向图 G 中顶点 i 到顶点 j 是否有路径,是则返回 1,否则返回 0 {

int visited MAXSIZE] InitQueue(Q) EnQueue(Q, 1) while(!Queue Empty(Q)) DeQueue(Q, u) sited=1 for(p=G vertices[i]. firstarc: p: p=p->nextarc) if(k-j return 1 if( visited [k] EnQueue(Q, k) i//for eturn 0 i/lexis BFS 724 void s traverse nonrecursive( Graph G∥非递归遍历强连通图G int visited MAXSIZe] Init Stack (S); Push( S Get vex(S,1),∥将第一个顶点入栈 Ⅴ isited=1 while(!Stack Empty(s)) while(gettop(s, I)&&i) First AdjVex(g, i) if(j&&!visited si(); visited Gll Push(Sj),∥向左走到尽头 i//while if(!StackEmpty(s)) Pop(sj) Gettop(s, 1) k= NextAdjVex(Gj)∥向右走一步 if(k&&!visited [kD)

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(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[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); //向左走到尽头 } }//while if(!StackEmpty(S)) { Pop(S,j); Gettop(S,i); k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {

visit(k) visited kF=1 Push(S, k); i//Traverse Nonrecursive 分析本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37由于 是强连通图所以从第一个结点出发一定能够访问到所有结点 725 见书后解答 7.2 Status TopoN( ALGraph G/按照题目要求顺序重排有向图中的顶点 int new MAXSIZE), indegree MAXSIZE]∥储存结点的新序号 FindInDegree(G, indegree); Init Stack(S) for(Fl; Knextarc) if(!(-indegreek]) Push(s, k); i//for i//while if(count< G. vexnum) return error;∥图中存在环 for(F1; K<=n; i++)printf("Old No: %d New No: %d\n", i, new[) eturn OK. M//TopoN 分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵 72 int visited MAXSIZe]

visit(k); visited[k]=1; Push(S,k); } }//if }//while }//Straverse_Nonrecursive 分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考 6.37.由于 是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7.25 见书后解答. 7.26 Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点 { int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号 n=G.vexnum; FindInDegree(G,indegree); InitStack(S); for(i=1;inextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); }//for }//while if(count<G.vexnum) return ERROR; //图中存在环 for(i=1;i<=n;i++) printf("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的简单路径 fir=j&&k=0) return1;∥找到了一条路径,且长度符合要求 else if(k>0) sited=I for(p=G vertices[i]. firstarc: p: p=p->nextarc) =p->adjvex; if(visited) st_path len(G, 1j, k1)em1:/剩余路径长度减一 ∥for isited[i=0;∥本题允许曾经被访问过的结点出现在另一条路径中 geese tumn0;/没找到 7.28 int path IMAXSIZE] visited MAXSIZE/暂存遍历过程中的路径 int Find all path( ALGraph G, int u, int v,intk∥/求有向图G中顶点u到v之间的所 有简单路径k表示当前路径长度 path]=u;,∥加入当前路径中 visited u]F= if(u==v)/找到了一条简单路径 printf("Found one path! n"); for(i=0path[计++) printf("d"path[,∥打印输出 else for(p=Gvertices[u]. firstarc: p: p=p->nextarc) =p->adjvex f(! visited叫) Find all pathe(GLvk+1);/继续寻找 visited u]=0; path=0;/回溯 i//Find All Path main

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]=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; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 7.28 int path[MAXSIZE],visited[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.vertices[u].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找 } visited[u]=0; path[k]=0; //回溯 }//Find_All_Path main() {