双连通图双联通图（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]; }传递闭包我们由一个问题引入传递闭包的概念。有一个边不带权值的有向图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。 |
