|
图的基本操作算法
查看(1799) 回复(0) |
|
 lyh2006
|
发表于 2010-08-24 00:04
楼主
1.void CreatGraph (AdjList g) //建立有n个顶点和m 条边的无向图的邻接表存储结构
{ int n,m; scanf("%d%d",&n,&m); for(i =1,i<=n;i++) //输入顶点信息,建立顶点向量 { scanf(&g.vertex); g.firstarc=null;} for(k=1;k<=m;k++) //输入边信息 { scanf(&v1,&v2); //输入两个顶点 i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位 p=(ArcNode *)malloc(sizeof(ArcNode)); //申请边结点 p->adjvex=j; p->next=g.firstarc; g.firstarc=p; //将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode)); //无向图双向连接 p->adjvex=i; p->next=g[j].firstarc; g[j].firstarc=p; } }//算法CreatGraph结束 2.void CreatAdjList(AdjList g) //建立有向图的邻接表存储结构 { int n; scanf("%d",&n); for (i=1;i<=n;j++) { scanf(&g.vertex); g.firstarc=null; }//输入顶点信息 scanf(&v1, &v2); while(v1 && v2) //题目要求两顶点之一为0表示结束 { i=GraphLocateVertex(g2,v1); p=(ArcNode*)malloc(sizeof(ArcNode)); //有向图 只需要单边 p->adjvex=j; p->next=g.firstarc; g.firstarc=p; scanf(&v1,&v2); } } 5．void InvertAdjList(AdjList gin,gout） //将有向图的出度邻接表改为按入度建立的逆邻接表 { for(i=1;i<=n;i++) //设有向图有n个顶点，建逆邻接表的顶点向量。 { gin.vertex=gout.vertex; gin.firstarc=null; } //逆邻接表 顶点初始化 for(i=1;i<=n;i++) //邻接表转为逆邻接表 { p=gout.firstarc; //取指向邻接表的指针 邻接表 头结点i的第一条边 while(p!=null) { j=p->adjvex; // 邻接表<i,j>边结点中的j顶点信息 s=(ArcNode *)malloc(sizeof(ArcNode)); //申请逆邻接表的边结点空间 s->adjvex=i; //对逆邻接表的<j,i>边结点 顶点信息赋值 s->next=gin[j].firstarc; //对逆邻接表的<j,i>边结点 下一边信息赋值 gin[j].firstarc=s; // <j,i>边结点链入逆邻接表 p=p->next; // 邻接表中找下一个邻接点。 }//while }//for } 6.void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //将图的邻接表表示转换为邻接矩阵表示 { for(i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。 for(j=1;j<=n;j++) gm[j]=0; for(i=1;i<=n;i++) { p=gl.firstarc; //取第一个邻接点。 while(p!=null) { gm[p->adjvex]=1; p=p->next; } //下一个邻接点 }//for }//算法结束 7.void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //图的邻接矩阵表示法转换为邻接表表示法 { for(i=1;i<=n;i++) //邻接表表头向量初始化。 { scanf(&gl.vertex); gl.firstarc=null; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(gm[j]==1) { p=(ArcNode *)malloc(sizeof(ArcNode)) ; //申请结点空间。 p->adjvex=j; //顶点i的邻接点是j p->next=gl.firstarc; //下一个邻接边结点 gl.firstarc=p; //链入顶点i的邻接点链表中 } }//end [算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。 9.void DeletEdge(AdjList g,int i,j) //在用邻接表方式存储的无向图g中，删除边(i,j) { p=g.firstarc; pre=null; //删顶点i 的边结点(i,j),pre是前驱指针 while(p) if(p->adjvex==j) //找到了要删除的结点 { if(pre==null) g.firstarc=p->next; //要删除的是第一个邻接点，重新设置第一邻接点 else pre->next=p->next; //要删除的不是第一邻接点 重新设置pre后链 跳过p 链上p->next free(p);} //释放结点空间。 else { pre=p; p=p->next;} //没找到，沿链表继续查找 p=g[j].firstarc; pre=null; //删顶点j 的边结点(j,i) while(p) if(p->adjvex==i) { if(pre==null)g[j].firstarc=p->next; else pre->next=p->next; free(p);}//释放结点空间。 else { pre=p; p=p->next;} //沿链表继续查找 }// DeletEdge [算法讨论] 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。 10.void DeleteArc（AdjList g,vertype vi,vj） //删除以邻接表存储的有向图g的一条弧<vi,vj>，假定顶点vi和vj存在 { i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //顶点定位 p=g.firstarc; pre=null; while(p) if(p->adjvex==j) { if(pre==null) g.firstarc=p->next; else pre->next=p->next; free(p);}//释放结点空间。 else { pre=p; p=p->next;} }//结束 不用再查找j 比无向图省事 ★★图的遍历算法★★ 12.在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 int count (AdjList g , int k ) //在n个顶点以邻接表表示的有向图g中，求指定顶点k(1<=k<=n)的入度。 { int count =0; for(i=1;i<=n;i++) //求顶点k的入度要遍历整个邻接表。 if(i!=k) //顶点k的邻接链表不必计算 { p=g.firstarc;//取顶点 i 的邻接边 while(p) { if(p->adjvex==k) count++; p=p->next; }//while }//if return(count); //顶点k的入度. } 8.在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag，初始化为0，若有通路，则flag=1。 算法1：int visited[]=0; //全局变量，访问数组初始化 int dfs(AdjList g , vertype vi ,vj) //以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无 { visited[vi]=1; //visited是访问数组，假设顶点的信息就是顶点编号。 p=g[vi].firstarc; //第一个邻接点。 while( p!=null) { j=p->adjvex; if (j==vj) { flag=1; return（1）;} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j,vj); //递归进行深度遍历 p=p->next； //遍历完返回，继续下一边 }//while if(!flag) return(0); //最后没有通路 返回0 }//结束 [算法讨论] 若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。下面算法2输出vi 到 vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。 算法2：void dfs(AdjList g , int i,j) //有向图g的顶点vi（编号i）和顶点vj（编号j）间是否有路径，如有，则输出。 { int top=0, stack[]; //stack是存放顶点编号的栈 visited=1; //visited 数组在进入dfs前已初始化。 stack[++top]=i; p=g.firstarc; //求第一个邻接弧结点. while(p) { if(p->adjvex==j) //弧p的顶点即为j，遇到顶点vj 输出路径 { stack[++top]=j; //顶点j入栈 printf( "顶点 vi 和 vj 的路径为： "); for(i=1; i<=top; i++) printf( "%4d",stack); exit(0); }//if else if (visited[p->adjvex]==0) //弧p的顶点p->adjvex尚未被访问 { dfs(g,p->adjvex,j); top--; p=p->next;} // 递归进行深度遍历 出栈 }//while }//结束算法2 算法3：本题用非递归算法求解。 int Connectij (AdjList g , vertype vi , vj ) //判断n个顶点以邻接表表示的有向图g中，顶点 Vi 各Vj 是否有路径，有则返回1，否则返回0。 { for(i=1;i<=n;i++) visited=0; //访问标记数组初始化。 i=GraphLocateVertex(g,vi); //顶点定位，不考虑 vi或 vj不在图中的情况。 j=GraphLocateVertex(g,vj); int stack[],top=0;stack[++top]=i; while(top>0) { k=stack[top--]; p=g[k].firstarc; while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k个链表中第一个未访问的弧结点。 if(p==null) top--; else { i=p->adjvex; if(i==j) return(1); //顶点vi和vj 间有路径。 else {visited=1; stack[++top]=i;}//else }//else }while return(0); } //顶点vi和vj 间无通路。 13.有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。 ●void Print(int v,int start ) //输出从顶点start开始的回路。 { for(i=1;i<=n;i++) if(g[v]!=0 && visited==1 ) //若存在边（v,i），且顶点i的状态为1。 { printf(“%d”,v); if(i==start) printf(“ ”); else Print(i,start); //递归 break;} ●void dfs(int v) { visited[v]=1; //0:未访问;1:已访问但其邻接点未访问完; 2:已访问且其邻接点已访问完 for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在边(v,j) if (visited[j]!=1) //0:未访问 或 2:已访问且其邻接点已访问完 { if(!visited[j]) dfs(j); } //0:未访问j未访问 深度遍历j else {cycle=1; Print(j,j);} // 1:已访问且其邻接点未访问完 visited[v]=2; //访问v完成 2:已访问且其邻接点已访问完 }//dfs ●void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 { for(i=1;i<=n;i++) visited=0; for(i=1;i<=n;i++ ) if(!visited) dfs(i); }//find_cycle 16.本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数; AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v) { visited[v]=1; num++; //访问的顶点数＋1 if(num==n) { printf(“%d是有向图的根。 ”,v); num=0;} //重新计数 p=g[v].firstarc; //第一边结点 while (p) { if(visied[p->adjvex]==0) dfs(p->adjvex); //未访问 递归深度遍历 p=p->next;} //while visited[v]=0; num--; //恢复顶点v 全局变量重新计数 便于后边遍历 }//dfs void JudgeRoot() //判断有向图是否有根，有根则输出之。 { static int i ; for(i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 { num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g.vertex。 17.图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。 void dfs () { visited[v]=1; printf (“%3d”,v); //输出连通分量的顶点。 p=g[v].firstarc; while(p!=null) { if（visited[p->adjvex]==0） dfs(p->adjvex); //深度递归访问 p=p->next; }//while }// dfs void Count() //深度优先遍历求图中连通分量的个数 { int k=0 ; static AdjList g ; //设无向图g有n个结点 for(i=1;i<=n;i++ ) if(visited==0) { printf (" 第%d个连通分量: ",++k); dfs(i);} }//Count 算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g.vertex分量输出。 18.void bfs(AdjList GL，vertype v ) //从v发非递归广度优先遍历以邻接表为存储结构的无向图GL。 { visited[v]=1; printf( "%3d",v); //输出第一个遍历的顶点。 QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大 while(!QueueEmpty(Q)) { v=QueueOut(Q); // v出队列。 p=GL[v].firstarc; // GL是全局变量，第一个邻接边结点 while(p!=null) { if(visited[p->adjvex]==0) //第一个邻接点未访问 { printf("%3d",p->adjvex); visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if //访问入队 p=p->next; //下一个邻接边结点 即广度优先 }//while }// while (!QueueEmpty(Q)) }//bfs void BFSCOM() //广度优先搜索，求无向图Ｇ的连通分量。 { int count=0; //记连通分量个数。 for (i=1;i<=n;i++) visited=0; for (i=1;i<=n;i++) if (visited==0) {printf(" 第%d个连通分量: ",++count); bfs(i);}//if }//BFSCOM 27.D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0) // 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。 { int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for(i=1,i<=n;i++) visited=0; //图有n个顶点，visited数组为全局变量 初始化 for(i=1,i<=n;i++) //对n个顶点的图g进行D_搜索 if(visited==0) //未访问 { s[++top]=i; visited=1; printf( "%3d",i); //入栈；访问 while(top>0) { i=s[top--]; //退栈，准备找邻接点 p=g.firstarc; //取第一个邻接边结点 while(p!=null) //处理顶点的所有邻接边结点 { j=p->adjvex; //邻接点 if(visited[j]==0) //未访问的邻接点 { visited[j]=1; printf( "%3d",i); s[++top]=j;} //访问并入栈 p=p->next; //广度优先遍历 } //下一个邻接点 }//while(top>0) } //if }//D_BFS 20. void Traver(AdjList g,vertype v) //图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。 { struct arc *stack[]; visited[v]=1；printf(v); //输出顶点v top=0; p=g[v].firstarc; stack[++top]=p; ★★while(top>0 || p!=null) {★while(p) if( p && visited[p->adjvex]) p=p->next; //已访问 找下一个 else{ printf(p->adjvex); visited[p->adjvex]=1; //访问 stack[++top]=p; p=g[p->adjvex].firstarc; //入栈 深度遍历 }//else ★if (top>0) { p=stack[top--]; p=p->next; } }//while }//算法结束。 [算法讨论] 以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是 for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi); 21. void dfs(v) { i=GraphLocateVertex(g ,v); //定位顶点 visited=1; printf(v); //输出顶点信息 p=g.firstarc; while(p) { if(visited[p->adjvex]==0) dfs(g[p->adjvex].vertex); p=p->next; }//while }//dfs void traver( ) //深度优先搜索的递归程序；以邻接表表示的图g是全局变量。 { for (i=1;i<=n;i++) visited=0; //访问数组是全局变量初始化。 for (vi=v1;vi<=vn;vi++) if (visited[GraphLocateVertex(g，vi)]==0) dfs(vi); }//算法结束。 23.对无向图Ｇ的深度优先遍历，将连通分量的顶点用括号括起来的算法。 void Traver( ) {for (i=1;i<=nodes(g);i++) visited=0; //visited是全局变量，初始化。 for (i=1;i<=nodes(g);i++) if (visied==0) { printf ("("); dfs(i); printf (")"); } }//Traver 24.void visit(vertype v) //访问图的顶点v。 int nodes(graph g) //图的顶点数 void initqueue (vertype Q[]) //图的顶点队列Ｑ初始化。 void enqueue (vertype Q[] ,v) //顶点v入队列Ｑ。 vertype delqueue (vertype Q[]) //出队操作。 int empty (Q) //判断队列是否为空的函数，若空返回１，否则返回０。 vertype firstadj(graph g ,vertype v)//图g中v的第一个邻接点。 vertype nextadj(graph g ,vertype v ,vertype w)//图g中顶点v的邻接点中在w后的邻接点 void bfs (graph g ,vertype v0) //利用上面定义的图的抽象数据类型，从顶点v0出发 广度优先遍历图g。 { visit(v0); visited[v0]=1; //设顶点信息就是编号，visited是全局变量。 initqueue(Q); enqueue(Q,v0); //v0入队列。 while(!empty(Q)) { v=delqueue(Q); //队头元素出队列。 w=firstadj(g ,v); //求顶点v的第一邻接点 while(w!=0) //w!=0表示w存在。 { if(visited[w]==0) //若邻接点未访问。 { visit(w); visited[w]=1; enqueue(Q,w); }//if w=nextadj(g,v,w); //求下一个邻接点。 }//while }//while }//bfs void Traver(graph g) //对图g进行宽度优先遍历，图g是全局变量。 { int n= nodes(g); for(i=1;i<=n;i++) visited=0; for(i=1;i<=n;i++) if (visited==0) bfs(i); } //Traver 25.使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。 void SPathdfs(v0) //判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。递归 { visited[v0]=1; path[++num]=v0; //访问起点v0，加入路径 if(num==nodes(G) //有一条简单路径，输出之。 { for(i=1;i<=num;i++) printf( "%3d",path); printf( " "); exit(0);} //if p=g[v0].firstarc; //取第一个邻接边结点 while (p) { if(visited[p->adjvex]==0) SPathdfs(p->adjvex); //未访问，递归深度优先遍历。 p=p->next; //下一个邻接点。 }//while visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs 26.非递归算法，顶点信息仍是编号。 void AllSPdfs(AdjList g,vertype u,vertype v) //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v) 非递归 { int top=0,s[]; s[++top]=u; visited=1; //起点加入路径，访问 while(top>0 || p) { p=g[s[top]].firstarc; //第一个邻接点。 while(p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接弧结点。 if(p==null) top--; //退栈。 else{ i=p->adjvex; //取邻接点（编号）。 if(i==v) //找到从u到v的一条简单路径，输出。 { for(k=1;k<=top;k++) printf( "%3d",s[k]); printf( "%3d ",v);} else{ visited=1; s[++top]=i; } //未找到 else深度优先遍历。 }//else }//while }// AllSPdfs 28.对有向无环图(DAG)的顶点，以整数适当编号后，可使其邻接矩阵中对角线以下元素全部为零。根据这一要求，可以按各顶点出度大小排序，使出度最大的顶点编号为1，出度次大者编号为2，出度为零的顶点编号为n。这样编号后，可能出现顶点编号i<j，但却有一条从顶点到j到i的弧。这时应进行调整，即检查每一条弧，若有<i,j>，且i>j，则使顶点j的编号在顶点i的编号之前。 void Adjust(AdjMatrix g1 ,AdjMatrix g2) //对以邻接矩阵存储的DAG图g1重新编号，使若有<i,j>，则编号i<j，重新编号后图以邻接矩阵g2存储。 { typedef struct { int vertex ,out ,count }node ; //结点结构：顶点，出度，计数。 node v[]; //顶点元素数组。 int c[]; //中间变量 ①for(i=1;i<=n;i++) //顶点信息数组初始化，设图有n个顶点。 { v.vertex=i; v.out=0; v.count=1; c=1; } //count=1为最小 ②for(i=1;i<=n;i++) //计算每个顶点的出度。 for (j=1;j<=n;j++) v.out+=g1[j]; ③for(i=n;i>=2;i--) //对v的出度域进行计数排序，出度大者，count域中值小。 for(j=i-1;j>=1;j--) if(v.count<=v[j].count) v.count++; else v[j].count++; ④for(i=1;i<=n;i++) //第二次调整编号。若<i,j>且i>j，则顶点j的编号在顶点i的编号之前 for(j=i;j<=n;j++) if(g1[j]==1 && v.count>v[j].count) { v.count=v[j].count; v[j].count++; } ⑤for(i=n;i>=2;i--)) //对v的计数域v.count排序，按count域从小到大顺序存到数组c中。 for(j=i-1;j>=1;j--) if(v.count<v[j].count) c[j]++; else c++; ⑥for(i=1;i<=n;i++) v.count=c; //将最终编号存入count 域中。 ⑦for(i=1;i<=n;i++) //赋值 for(j=1;j<=n;j++) g2[v.count][v[j].count]=g1[v.vertex][v[j].vertex]; }//算法结束 29.将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) //判断以邻接矩阵表示的图g是否是二部图。 { int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合） int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。 int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组 for (i=1;i<=n;i++) { visited=0; s=0; } //初始化，各顶点未确定属于那个集合 Q[1]=1; r=1; s[1]=1; //顶点1放入集合S1 while(f<r) { v=Q[++f]; if (s[v]==1) jh=2; else jh=1; //准备v的邻接点的集合号 if(!visited[v]) //未访问v则访问之 {visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中 for(j=1,j<=n;j++) //对v的每一边<i,j>检查邻接点j if(g[v][j]==1) //连通 有边 { if(!s[j]) { s[j]=jh; Q[++r]=j; } //二部图 邻接点入队列 else if(s[j]==s[v]) return(0); } //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。 30.连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 { typedef struct { int i,j,w }node; //设顶点信息就是顶点编号，权是整型数 node edge[]; scanf( "%d%d",&e,&n) ; //输入边数和顶点数。 for(i=1;i<=e;i++) //输入e条边：顶点，权值。 scanf("%d%d%d" ,&edge.i ,&edge.j ,&edge.w); for(i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 { edge[0]=edge; j=i-1; while(edge[j].w<edge[0].w) edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for k=1; eg=e; while(eg>=n) //破圈，直到边数e=n-1. { if(connect(k)) //删除第k条边若仍连通。 { edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入dfs或bfs就可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第17,18就是测连通分量个数的算法。 31.求单源点最短路径问题，存储结构用邻接表表示，这里先给出所用的邻接表中的边结点的定义： struct node { int adjvex,weight; struct node *next; }p; void Shortest_Dijkstra(AdjList cost ,vertype v0) //在带权邻接表cost中，用Dijkstra方法求从顶点v0到其它顶点的最短路径。 { int dist[],s[]; //dist数组存放最短路径，s数组存顶点是否找到最短路径的信息。 for(i=1;i<=n;i++) {dist=INFINITY; s=0; } //初始化，INFINITY是机器中最大的数 s[v0]=1; p=g[v0].firstarc; while(p) //顶点的最短路径赋初值 { dist[p->adjvex]=p->weight; p=p->next;} for(i=1;i<n;i++) //在尚未确定最短路径的顶点集中选有最短路径的顶点u { mindis=INFINITY; //INFINITY是机器中最大的数，代表无穷大 ●for(j=1;j<=n;j++) if(s[j]==0 && dist[j]<mindis) { u=j; mindis=dist[j]; } ●s=1; //顶点u已找到最短路径。 p=g.firstarc; ●while(p) //修改从v0到其它顶点的最短路径 { j=p->adjvex; if(s[j]==0 && dist[j]>dist+p->weight) dist[j]=dist+p->weight; p=p->next; } }// for (i=1;i<n;i++) 这里只是执行n-1次 循环内容与i无关 }//Shortest_Dijkstra 39.按Dijkstra路径增序求出源点和各顶点间的最短路径，上面已有。求出最小生成树，即以源点为根，其路径权值之和最小的生成树。在确定顶点的最短路径时，总是知道其（弧出自的）前驱（双亲）顶点，可用向量p[1..n]记录各顶点的双亲信息，源点为根，无双亲，向量中元素值用-1表示。 void Shortest_PTree ( AdjMatrix G, vertype v0) //利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G的最小生成树 { int d[] ,s[] ; //d数组存放各顶点最短路径，s数组存放顶点是否找到最短路径。 int p[] ; //p数组存放顶点在生成树中双亲结点的信息。 for(i=1;i<=n;i++) //初始化 { d=G[v0]; s=0; if(d<MAXINT) p=v0; //MAXINT是机器最大数，v0是i的前驱（双亲）。 else p=-1; }//for //i目前无前驱，p数组各量初始化为-1。 s[v0]=1; d[v0]=0; p[v0]=-1; //从v0开始，求其最小生成树。 ★for(i=1;i<n;i++) { mindis=MAXINT; ●for(j=1;j<=n;j++) if(s[j]==0 && d[j]<mindis) //尚未找到最短 有通路 { u=j; mindis=d[j];} //for循环查找 直到最小 ●s=1; //顶点u已找到最短路径。 ●for(j=1;j<=n;j++) //修改j的最短路径及双亲。 if (s[j]==0 && d[j]>d+G[j]) {d[j]=d+G[j]; p[j]=u;} }//for (i=1;i<=n;i++) ★for(i=1;i<=n;i++) //输出最短路径及其长度，路径是逆序输出。 if(i!=v0) { pre=p; printf( " 最短路径长度＝%d，路径是：%d，",d,i); while(pre!=-1) { printf( ",%d",pre); pre=p[pre]; } //一直回溯到根结点。 }//if }//算法结束 32. FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) //求具有n个顶点的有向图每对顶点间的最短路径 { AdjMatrix length; //length[j]存放顶点vi到vj的最短路径长度。 for (i=1;i<=n;i++) for (j=1;j<=n;j++) length[j]=g[j]; //初始化。 for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (length[k]+length[k][j]<length[j]) length[j]=length[k]+length[k][j]; }//算法结束 35.用宽度优先遍历求解。若以v0作生成树的根为第1层，则距顶点v0最短路径长度为K的顶点均在第K+1层。可用队列存放顶点，将遍历访问顶点的操作改为入队操作。队列中设头尾指针f和r，用level表示层数。 void bfs_K ( graph g ,int v0 ,K) //输出无向连通图g（未指定存储结构）中距顶点v0最短路径长度为K的顶点。 { int Q[]; //Q为顶点队列，容量足够大。 int f=0,r=0,t=0; //f和r分别为队头和队尾指针，t指向当前层最后顶点。 int level=0,flag=0; //层数和访问成功标记。 visited[v0]=1; //设v0为根。 Q[++r]=v0; t=r; level=1; //v0入队。 ★★while(f<r && level<=K+1) { v=Q[++f]; //出队头 w=GraphFirstAdj(g,v); ★while(w!=0) //w!=0 表示邻接点存在 { if (visited[w]==0) //未访问 { Q[++r]=w; visited[w]=1; //邻接点入队列尾 访问 if(level==K+1) { printf("距顶点v0最短路径为k的顶点%d ",w); flag=1; } //成功访问 }//if w=GraphNextAdj(g ,v ,w); //广度遍历 }//while(w!=0) ★if(f==t) { level++；t=r; } //当前层处理完，修改层数，t指向下一层最后一个顶点 }//while(f<r && level<=K+1) ★★if(flag==0) printf( "图中无距v0顶点最短路径为%d的顶点。 ",K); }//算法结束。 [设法讨论]亦可采取另一个算法。由于在生成树中结点的层数等于其双亲层次数加1，故可设顶点和层次数2个队列，其入队和出队操作同步，其核心语句段如下： QueueInit(Q1) ; QueueInit(Q2); //Q1和Q2是顶点和顶点所在层次数的队列。 visited[v0]=1; //访问数组初始化，置v0被访问标记。 level=1; flag=0; //是否有层次为K的顶点的标志 QueueIn(Q1,v0); QueueIn(Q2,level); //顶点和层数入队列。 ★while(!empty(Q1) && level<=K+1) { v=QueueOut(Q1); level=QueueOut(Q2);//顶点和层数出队。 w=GraphFirstAdj(g,v0); ▲while(w!=0) //邻接点存在。 { if(visited[w]==0) if(level==K+1) { printf("距离顶点v0最短路径长度为K的顶点是%d ",w); visited[w]=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); }//if w=GraphNextAdj(g ,v ,w); }//while(w!=0) }//while(!empty(Q1) && level<K+1) ★if (flag==0) printf( "图中无距v0顶点最短路径为%d的顶点。 ",K); 37.利用FLOYD算法求出每对顶点间的最短路径矩阵w，然后对矩阵w，求出每列j的最大值，得到顶点j的偏心度。然后在所有偏心度中，取最小偏心度的顶点v就是有向图的中心点。 void FLOYD_PXD(AdjMatrix g) //对以带权邻接矩阵表示的有向图g，求其中心点。 { AdjMatrix w=g ; //将带权邻接矩阵复制到w。 for(k=1;k<=n;k++) //求每对顶点间的最短路径。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if( w[j]>w[k]+w[k][j]) w[j]=w[k]+w[k][j]; v=1; dist=MAXINT; //中心点初值顶点v为1，偏心度初值为机器最大数。 for(j=1;j<=n;j++) { s=0; for(i=1;i<=n;i++) if(w[j]>s) s=w[j]; //求每列中的最大值为该顶点的偏心度 if(s<dist) { dist=s; v=j; }//各偏心度中最小值为中心点 }//for printf( "有向图g的中心点是顶点%d,偏心度%d ",v,dist); }//算法结束 41.对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。这里设定visited访问数组和finished数组为全局变量，若finished=1,表示顶点i的邻接点已搜索完毕。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。 int visited[]=0; finished[]=0; flag=1; //flag测试拓扑排序是否成功 ArcNode *final=null; //final是指向顶点链表的指针，初始化为0 void dfs(AdjList g,vertype v) //以顶点v开始深度优先遍历有向图g，假定顶点信息就是顶点编号. { ArcNode *t; //指向边结点的临时变量 printf("%d",v); visited[v]=1; p=g[v].firstarc; while(p!=null) { j=p->adjvex; if(visited[j]==1 && finished[j]==0) //已访问 未搜索完 flag=0 //dfs结束前出现回边 else if(visited[j]==0) //未访问 { dfs(g,j); finished[j]=1; } //递归访问 j的递归退出后 对j搜索完成 p=p->next; }//while t=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点 t->adjvex=v; t->next=final; final=t; //将该顶点插入链表 } //dfs结束 int dfs-Topsort(Adjlist g) //对以邻接表为存储结构的有向图进行拓扑排序，拓扑排序成功返回1，否则返回0 { i=1; while(flag && i<=n) if(visited==0) { dfs(g,i); finished=1; } //if return(flag); }// dfs-Topsort 42.地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。 void MapColor(AdjMatrix C) //以邻接矩阵C表示的n个国家的地区涂色 { int s[]; //栈的下标是国家编号，内容是色数 s[1]=1； //编号01的国家涂1色 i=2;j=1; //i为国家号，j为涂色号 ★while(i<=n) {▼while(j<=4 && i<=n) //4色定理 { k=1; //k指已涂色区域号 ●while(k<i && s[k]*C[k]!=j) k++; //判相邻区是否已涂色 ●if(k<i) j=j+1; //用j+1色继续试探 else { s=j; i++; j=1;}//与相邻区不重色，涂色结果进栈，继续对下一区涂色试探 进栈;j重新开始试探 }//while (j<=4 && i<=n) ▲if(j>4) { i--; j=s+1;} //退栈 变更栈顶区域的颜色。 }//while }//结束MapColor 36. 对于无环连通图，顶点间均有路径，树的直径是生成树上距根结点最远的两个叶子间的距离，利用深度优先遍历可求出图的直径。 int dfs(Graph g ,vertype parent ,vertype child ,int len) //深度优先遍历，返回从根到结点child所在的子树的叶结点的最大距离。 {current_len=len; maxlen=len; v=GraphFirstAdj(g ,child); while (v!=0) //邻接点存在。 if (v!=parent) {len=len+length(g ,child ,c); dfs(g ,child ,v ,len); if (len>maxlen) maxlen=len; v=GraphNextAdj(g ,child ,v); len=current_len; } //if len=maxlen; return(len); }//结束dfs。 int Find_Diamenter (Graph g) //求无向连通图的直径，图的顶点信息为图的编号。 {maxlen1=0; maxlen2=0; //存放目前找到的根到叶结点路径的最大值和次大值。 len=0; ///深度优先生成树根到某叶结点间的距离 w=GraphFirstAdj(g,1); //顶点１为生成树的根。 while (w!=0) //邻接点存在。 {len=length(g ,1 ,w); if (len>maxlen1) {maxlen2=maxlen1; maxlen1=len;} else if (len>maxlen2) maxlen2=len; w=GraphNextAdj(g ,1 ,w);//找顶点1的下一邻接点。 }//while printf( "无向连通图g的最大直径是%d " ,maxlen1+maxlen2); return(maxlen1+maxlen2); }//结束find_diamenter 算法主要过程是对图进行深度优先遍历。若以邻接表为存储结构，则时间复杂度为O(n+e)。 FUNC find_diameter( g: Graph):integer; {利用深度优先遍历方法求出根结点到每一个叶结点的距离，maxlen1存放的是目前找到根到叶结点的最大值，maxlen2存放的是目前找到根到叶结点的次大值，len记录深度优先遍历中到某一叶结点的距离，设图g的顶点编号为1到vtxnum，以顶点1为根生成深度优先树} maxlen1:=0; maxlen2:=0; len:=0; w:=firstadj(g，1) {w为顶点1的邻接点} WHILE w!=0 DO BEGIN {当邻接点存在时} len:=length(g，1，w) {顶点1到顶点w的距离} dfs(g，1，w，len); IF len > maxlen1 THEN BEGIN maxlen2:=maxlen1; maxlen1:=len; END ELSE IF len > maxlen2 maxlen2:=len w:=nextdaj(g，1，w); END return(maxlen1+maxlen2); ENDF;{find_diameter} PROC dfs(g:Graph; parent，child:vtxptr; VAR len:integer); { dfs返回时，len中存放的是从根到结点child所在的子树的叶结点的最大距离} current_len:=len; {保存到当前结点的路径长度} maxlen:=len; v:=firstadj(g，child); WHILE v!=0 DO BEGIN IF v=parent CONTINUE; len:=len+length(g，child，v); dfs(g，child，v，len); IF len>maxlen THEN maxlen:=len; v:=nextadj(g，child.v); len:=current_len; END len:=maxlen; ENDP;{dfs} 算法的主要过程是对图g进行深度优先遍历，若图g以邻接表的形式存储，则时间复杂度为O(n+e)。 40.由关节点定义及特性可知，若生成树的根有多于或等于两棵子树，则根结点是关节点；若生成树某非叶子顶点v，其子树中的结点没有指向v的祖先的回边，则v是关节点。因此，对图G＝(v,{Edge})，将访问函数visited[v]定义为深度优先遍历连通图时访问顶点v的次序号，并定义一个low( )函数： low(v)＝Min(visited[v],low[w],visited[k]) 其中(v,w)∈Edge，(v,k)∈Edge，w是v在深度优先生成树上的孩子结点，k是v在深度优先生成树上的祖先结点。在如上定义下，若low[w]>=visited[v]，则v是根结点，因w及其子孙无指向v的祖先的回边。由此，一次深度优先遍历连通图，就可求得所有关节点。 int visited[] ,low[]; //访问函数visited和low函数为全局变量。 int count; //记访问顶点个数。 AdjList g; //图g以邻接表方式存储 void dfs_articul(vertype v0) //深度优先遍历求关节点。 {count++; visited[v0]=count; //访问顶点顺序号放入visited min=visited[v0]; //初始化访问初值。 p=g[v0].firstarc; //求顶点v的邻接点。 while (p!=null) {w=p->adjvex; //顶点v的邻接点。 if (visited[w]==0) //w未曾访问，w是v0的孩子。 {dfs_articul(g ,w); if (low[w]<min) min =low[w]; if (low[w]>=visited[v0]) printf(g[v0].vertex); //v0是关节点。 }//if else //w已被访问，是v的祖先。 if (visited[w]<min) min=visited[w]; p=p->next; }//while low[v0]=min; }//结束dfs_articul void get_articul( ) //求以邻接表为存储结构的无向连通图g的关节点。 {for (vi=1;vi<=n;vi++) visited[vi]=0; //图有n个顶点，访问数组初始化。 count=1; visited[1]=1; //设邻接表上第一个顶点是生成树的根。 p=g[1].firstarc; v=p->adjvex; dfs_articul(v); if (count<n) //生成树的根有两棵以上子树。 {printf(g[1].vertex);//根是关节点 while(p->next!=null) {p=p->next; v=p->adjvex; if(visited[v]==0) dfs-articul(v); }//while }//if }//结束get-articul //DFSArticul()公有成员函数 //递归:从v0出发,通过深度优先遍历当前图, //查找并输出该深度优先生成树上的所有关节点 //算法描述概要:定义了dfn[]函数,存放结点的DFS遍历 //序数,low[]函数存放通过,当前结点可以 ///////////////////////////////////////////////// template<class T,class E> int Graphlink<T,E>:  FSArticul(int v0,int* dfn,int* low){ static int count=0; //得到DFS序数的计数器 count++; int min=count; //当前访问的结点v0的DFS序数 dfn[v0]=count; //得到当前访问顶点的DFS序数 for(int ptr=getFirstNeighbor(v0) ;ptr!=-1 //遍历结点v0所有的邻接结点 ;ptr=getNextNeighbor(v0,ptr)) { int w=ptr; //w是v0的邻接结点,w也是v0的子结点 if(dfn[w]==0) //如果v0的子结点w没有被访问过 { DFSArticul( //递归:对以w为开始顶点的子图进行递归求关节点 w,dfn,low); if(low[w]<min) //退出递归以后,如果子结点u能达到的顶点DFS序数比 min=low[w]; //比v0能达到的更小 if(low[w]>=dfn[v0])//如果子结点u所能到达的顶点的DFS序数还没有v0大 cout<<v0<<":" //说明v0就是一个关节点 <<getValue(v0) <<"是一个关节点."<<endl; } else if(dfn[w]<min) //如果w的DFS序数比当前v0的最小回边系数更小 min=dfn[w]; //说明w已经在v0之前访问过了<v0,w>是一条回边 } low[v0]=min; //得到当前结点v0的low[]函数值 return count; //返回当前遍历过的顶点的个数 }; /////////////////////DFSArticul()公有成员函数结束 //FindArticul()公有成员函数 //调用DFSArticul()函数找出当前图的 //所有的关节点,并显示出来,思想：首先判断根结点 //是否有多于一个子树,如果是说明根也是关节点，然后 //以根的每棵子树根结点为起点继续找关节点 ///////////////////////////////////////////////// template<class T,class E> void Graphlink<T,E>::FindArticul() { int n=numVertices; int* dfn=new int[n]; //dfn[]函数的数组 int* low=new int[n]; //low[]函数的数组 for(int i=0;i<n;i++) //初始化dfn[]函数 dfn=0; dfn[0]=1; //以0号顶点为遍历的根结点 int p=getFirstNeighbor(0); //获取根结点0的第一个子结点 int k=DFSArticul(p,dfn,low);//对第一棵子树进行寻找,得到第一棵子树顶点个数 if(k!=n-1) //如果顶点个数不是总顶点数-1 { //怎说明根结点是关节点 cout<<0<<":"<<getValue(0) <<"是一个关节点."<<endl; p=getNextNeighbor(0,p); //获得子树p的兄弟子树 while(p!=-1) //对其他的子树进行再次的关节点寻找 { if(dfn[p]==0) //如果p还没有被访问过,就从该顶点开始寻找 DFSArticul(p,dfn,low); p=getNextNeighbor(0,p); }; }; }; |
|
回复话题 |
||
| 上传/修改头像 |
|
|
|