Board logo

标题: 图论算法 有图有代码 万字总结 向前辈致敬（3） [打印本页]
作者: yuyang911220    时间: 2016-8-20 19:47     标题: 图论算法 有图有代码 万字总结 向前辈致敬（3）

双连通图双联通图（biconnected graph）是没有关节点的连通图。对此有一个比较重要的公式如下：
low(u) = min{dfn(u), min{low(w)|w是u的儿子}, min{dfn(w)|(u,w)是一条回退边} }回退边也叫back edge，大家顾名思义就好，下面有更多应用。
下面来段求解图的双连通分支的算法：
void bicon(int u, int v) {     node_pointer ptr;     int w,x,y;     dfn=low=num++;     for(ptr=graph;ptr;ptr=ptr->link)     {         w=ptr->vertex;         if(v!=w && dfn[w]<dfn)                    add(&top,u,w);         if(dfn[w]<0)         {             bicon(w,u);             low=MIN2(low,low[w]);             if(low[w]>=dfn)             {                 printf("New biconnected component: ");                 do                 {                     delete(&top,&x,&y);                     printf(" <%d,%d>",x,y);                 }while(!((x==u)&&(y==w)));                 printf("n");             }         }         else if(w!=v)             low=MIN2(low,dfn[w]);     } }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
拓扑排序拓扑排序（topological sort）是对有向无环图的顶点的一种排序，它使得如果存在一条从vi到vj的路径，那么在排序中vj出现在vi的后面。正是由于这个特性，如果图含有回路，那么拓扑排序是不可能的。

拓扑排序简单的说，就是将上图变成下图。

求拓扑排序算法的一种简单方式：选中一个没有入边的顶点，显示出该点，并将它和它的边一起从图中删除，然后对图的其余部分应用同样的方法处理。
假设每一个顶点的入度被存储且图被读入一个邻接表中，下面的代码则可以生成一个拓扑排序。

对上图应用拓扑排序的结果如下：

最短路径算法单源最短路径问题：给定一个加权图G=（V，E）和一个特定顶点s作为输入，找出从s到G中每一个其他点的最短加权路径。
如下图所示，从v1到v6的最短加权路径的值为6（v1−v4−v7−v6），从v2到v5的最短加权路径的值为5（v2−v4−v5）。

下面这个图从v5到v4的最短加权路径可就有意思了，它是1么？不是。按照v5−v4−v2−v5−v4的路径走则是一条更短的路径了，因为这是带负值回路的图。而由于带负值而引入的循环，这个循环叫做负值回路（negative-cost cycle），当它出现在图中时，最短路径问题就是不确定的了。有负值的边未必不好，但它们明显使问题更加难了。

当未指明所讨论的是加权路径还是无权路径时，如果图是加权的，那么路径就是加权的。
下面列出单源最短路径算法：
void shortestpath(int v,int cost[][MAX_VERTICES],int distance[],int n,short int found[]) {     int i,u,w;     for(i=0;i<n;i++)     {         found=FALSE;         distance=cost[v];     }     found[v]=TRUE;     distance[v]=0;     for(i=0;i<n-2;i++)     {         u=choose(distance,n,found);         found=TRUE;         for(w=0;w<n;w++)             if(!found[w])                 if(distance+cost[w]<distance[w])                     distance[w]=cost[w]+distance;     } }  int choose(int distance[],int n,short int found[]) {     int i,min,minpos;     min=INT_MAX;     minpos=-1;     for(i=0;i<n;i++)         if(distance<min && !found)         {             min=distance;             minpos=i;         }     return minpos; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
思考：找出A到所有其他顶点的最短路径以及B到所有其他顶点的最短无权路径。

如果要求所有顶点对之间的最短路径，可以用下面这个算法：
void allcosts(int cost[][MAX_VERTICES],int distance[][MAX_VERTICES],int n) {     int i,j,k;     for(i=0;i<n;i++)         for(j=0;j<n;j++)             distance[j]=cost[j];     for(k=0;k<n;k++)         for(i=0;i<n;i++)             for(j=0;j<n;j++)                 if(distance[k]+distance[k][j]<distance[j])                     distance[j]=distance[k]+distance[k][j]; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
传递闭包我们由一个问题引入传递闭包的概念。有一个边不带权值的有向图G，要判断任意两个顶点i 和j 之间是否存在一条路径，此处有两种情况，一种是路径长度为正数，一种是路径长度为非负。以上两种情况分别被称为图的传递闭包（transitive closure），和自反传递闭包（reflexive transitive closure）。
传递闭包矩阵（transitive closure matrix）是一个矩阵，记作A+，如果从顶点i到j存在一条长度大于0的路径，则A+[j]=1，否则A+[j]=0。
自反传递闭包矩阵是一个矩阵，记作A∗，如果从顶点i到j存在一条长度大于0的路径，则A∗[j]=1，否则A∗[j]=0。



欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0