首页 > 代码库 > 图的算法

图的算法

因为图算法的各种英文名傻傻分不清楚,所以总结一下。

求最小生成树:

Kruskal

假设给定一个加权连通图G,G的边集合为E,顶点个数为n,要求其一棵最小生成树T。

假设T中的边和顶点均涂成红色,其余边为白色。开始时G中的边均为白色。

1)将所有顶点涂成红色;

2)在白色边中,挑选一条权最小的边,使其与红色边不形成圈,将该白色边涂红;

3)重复2)直到有n-1条红色边,这n-1条红色边便构成最小生成树T的边集合。

prime算法

1.清空生成树,任取一个顶点加入生成树

2.在那些一个端点在生成树里,另一个端点不在生成树里的边中,选取一条权最小的边,将它和另一个端点加进生成树

3.重复步骤2,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树

求最短路径:
       单源最短路径

(1)通用(Bellman-Ford算法):第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。即对于每一条边e(u, v),如果Distant[u] + w(u, v) <Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;
第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:
d(v) > d (u) + w(u,v)
若返回false,表示途中存在从源点可达的权为负的回路。
(2) 无负权边的图(Dijkstra算法)
                            
      所有结点间最短路径:
 (1) Floyd-Warshall算法:

 void Floyd(){
     int i,j,k;
     for(k=1;k<=n;k++)
         for(i=1;i<=n;i++)
             for(j=1;j<=n;j++)
                 if(dist[i][k]+dist[k][j]<dist[i][j])
                     dist[i][j]=dist[i][k]+dist[k][j];
 }

(2) Johnson算法:http://blog.csdn.net/xlf13872135090/article/details/17884301

图的算法