第七章 图 7.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{ InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;mnextarc;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上插入边(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.arcnum++; } 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;iadjvex=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))<0) return ERROR; n=G.vexnum; for(i=0;itailvex==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 }//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))<0) return ERROR; if((j=LocateVex(G,w))<0) 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[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(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;mivex=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) { 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;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,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[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(count0) { 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(){ ... Find_All_Path(G,u,v,0); //在主函数中初次调用,k值应为0 ...}//main 7.29 int GetPathNum_Len(ALGraph G,int i,int j,int len)//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数{ if(i==j&&len==0) return 1; //找到了一条路径,且长度符合要求 else if(len>0) { sum=0; //sum表示通过本结点的路径数 visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return sum;}//GetPathNum_Len 7.30 int visited[MAXSIZE];int path[MAXSIZE]; //暂存当前路径int cycles[MAXSIZE][MAXSIZE]; //储存发现的回路所包含的结点int thiscycle[MAXSIZE]; //储存当前发现的一个回路int cycount=0; //已发现的回路个数 void GetAllCycle(ALGraph G)//求有向图中所有的简单回路{ for(v=0;vnextarc) { w=p->adjvex; if(!visited[w]) DFS(G,w,k+1); else //发现了一条回路 { 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=0;i--) //第二次逆向的深度优先遍历 { v=finished(i); if(!visited[v]) { printf("\n"); //不同的强连通分量在不同的行输出 DFS2(G,v); } }//for}//Get_SGraph void DFS1(OLGraph G,int v)//第一次深度优先遍历的算法{ 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数组}//DFS1 void DFS2(OLGraph G,int v)//第二次逆向的深度优先遍历的算法{ 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分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为O(n+e). 7.32 void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储{ for(j=0;jnextarc) if(p->adjvex==k) closedge[j].lowcost=p->cost; }//if closedge[k].lowcost=0; for(i=1;inextarc) if(p->costadjvex].lowcost) closedge[p->adjvex]={k,p->cost}; }//if else Forest_Prim(G,k); //对另外一个连通分量执行算法 }//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(CSTNode)); 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 //双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q; //作为双亲最后一个孩子的兄弟 }}//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; //结点所属的连通分量号 } VexInfo;VexInfo vexs[MAXSIZE]; //记录结点所属连通分量号的数组 void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化{ for(i=0;i1) { 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--; } 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; //作为双亲的第一个孩子 else //双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q; //作为双亲最后一个孩子的兄弟 }}//Addto_CSTree分析:本算法使用一维结构体变量数组来表示等价类,每个连通分量所包含的所有结点属于一个等价类.在这个结构上实现了初始化,判断元素是否等价(两个结点是否属于同一个连通分量),合并等价类(连通分量)的操作. 7.34 Status TopoSeq(ALGraph G,int new[ ])//按照题目要求给有向无环图的结点重新编号,并存入数组new中{ int indegree[MAXSIZE]; //本算法就是拓扑排序 FindIndegree(G,indegree); Initstack(S); for(i=0;inextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); } }//while if(countnextarc) { w=p->adjvex; if(!visited[w]) DFS(G,w); }}//DFS 7.36 void Fill_MPL(ALGraph &G)//为有向无环图G添加MPL域{ FindIndegree(G,indegree); for(i=0;inextarc) { j=p->adjvex; if(G.vertices[j].MPL==0) k=Get_MPL(G,j); if(k>max) max=k; //求其直接后继顶点MPL的最大者 } G.vertices[i]=max+1;//再加一,就是当前顶点的MPL return max+1; }//else}//Get_MPL 7.37 int maxlen,path[MAXSIZE]; //数组path用于存储当前路径int mlp[MAXSIZE]; //数组mlp用于存储已发现的最长路径 void Get_Longest_Path(ALGraph G)//求一个有向无环图中最长的路径{ maxlen=0; FindIndegree(G,indegree); for(i=0;imaxlen&&!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;}//DFS 7.38 void NiBoLan_DAG(ALGraph G)//输出有向无环图形式表示的表达式的逆波兰式{ FindIndegree(G,indegree); for(i=0;iadjvex); PrintNiBoLan_DAG(G,p->nexarc->adjvex); printf("%c",c); }}//PrintNiBoLan_DAG 7.39 void PrintNiBoLan_Bitree(Bitree T)//在二叉链表存储结构上重做上一题{ 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)//给有向无环图表示的表达式求值{ FindIndegree(G,indegree); for(i=0;i