最小生成树（prime算法 & kruskal算法）和 最短路径算法（floyd算法 & dijkstra算法）

一、主要内容：

　　介绍图论中两大经典问题：最小生成树问题以及最短路径问题，以及给出解决每个问题的两种不同算法。

其中最小生成树问题可参考以下题目：

题目1012：畅通工程 http://ac.jobdu.com/problem.php?pid=1012

题目1017：还是畅通工程 http://ac.jobdu.com/problem.php?pid=1017

题目1024：畅通工程 http://ac.jobdu.com/problem.php?pid=1024

题目1028：继续畅通工程 http://ac.jobdu.com/problem.php?pid=1028

 

其中最短路径问题可参考一下题目：

 

题目1447：最短路 题目链接：http://ac.jobdu.com/problem.php?pid=1447

 

题目1008：最短路径问题 题目链接：http://ac.jobdu.com/problem.php?pid=1008

 

二、最小生成树与最短路径的定义与区别

      带权图分为有向图和无向图。

      无向图的最短路径又叫做最小生成树，有prime算法（普里姆算法）和kruskal算法（克鲁斯卡尔算法）；

      有向图的最短路径算法有floyd算法（弗洛伊德算法）和dijkstra算法（迪杰斯特拉）。

　　生成树的概念：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则 将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。

　　权最小的生成树称为最小生成树，常用的算法有prime算法和kruskal算法。

　　最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有：floyd算法和dijkstra算法。

三、构造最小生成树的算法

　　构造最小生成树一般使用贪心策略，有prime算法和kruskal算法。

　　prime算法的基本思想：

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

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

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

 

int prime(int cur)
{
    int index = cur;
    int sum = 0;
    memset(visit, false, sizeof(visit));
    visit[cur] = true;
    for(int i = 0; i < m; i ++){
        dist[i] = graph[cur][i];    
    }
    
    for(int i = 1; i < m; i ++){
        
        int mincost = INF;
        for(int j = 0; j < m; j ++){
            if(!visit[j] && dist[j] < mincost){
                mincost = dist[j];
                index = j;    
            }    
        }
        
        visit[index] = true;
        sum += mincost;
        
        for(int j = 0; j < m; j ++){
            if(!visit[j] && dist[j] > graph[index][j]){
                dist[j] = graph[index][j];
            }    
        }    
    } 
    return sum;    
}

　kruskal算法的基本思想：

　　1. 首先我们把所有的边按照权值先从小到大排列；

　　2. 接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。

　　其中用到了数据结构中的并查集。有关并查集的操作可以参考博客 http://blog.csdn.net/luomingjun12315/article/details/47373345

　　kruskal算法讲解推荐博客 http://www.cnblogs.com/skywang12345/p/3711500.html#anchor6

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#define MAX_SIZE 1010
 
using namespace std;
 
int n, m;
int Tree[MAX_SIZE];
 
int findRoot(int x){//find the root of x
    if(Tree[x]==-1) return x;
    else{
        int tmp = findRoot(Tree[x]);//continue the find
        Tree[x] = tmp;//change the root of x to tmp
        return tmp;
    }
     
}
int main(){
    while(scanf("%d",&n)!=EOF && n!=0){//when n==0 and jump out of the loop
        scanf("%d",&m);
        for(int i = 1 ; i <= n ; i++)//init
            Tree[i] = -1;
         
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            a = findRoot(a);//find the root of a
            b = findRoot(b);//find the root of b
            if(a!=b) Tree[a]=b;//merge those two sets to the same aggregates
        }
         
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++){
            if(Tree[i]==-1) ans++;//calculate the total numbers of aggregates
        }
        printf("%d\n",ans-1);
    }
    return 0;
}

四、最短路径算法

　　最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有：floyd算法和dijkstra算法。

　　floyd算法是最简单的最短路径算法，可以计算图中任意两点间的最短路径;

　　folyd算法的时间复杂度是O(N3),如果是一个没有边权的图，把相连的两点之间的距离设为dist[i][j] = 1，不相连的两点设为无穷大，用 floyd算法可以判断i,j两点是否有路径相连。

　　

void floyd()
{
    for(int k = 0; k < n; k ++){ //作为循环中间点的k必须放在最外一层循环 
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];    //dist[i][j]得出的是i到j的最短路径 
                }     
            }    
        }    
    }    
}

　　dijkstra算法用来计算从一个点到其他所有点的最短路径的算法，复杂度O(N2)。

void dijkstra(int s)   //s是起点
{
    memset(visit, false, sizeof(visit));    
visit[s] = true;
    for(int i = 0; i < n; i ++){
        dist[i] = graph[s][i];
    }
     
    int index;
    for(int i = 1; i < n; i ++){
        int mincost = INF;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] < mincost){
                mincost = dist[j];
                index = j;    
            }    
        }
        visit[index] = true;
        for(int j = 0; j < n; j ++){
            if(!visit[j] && dist[j] > dist[index] + graph[index][j]){
                dist[j] = dist[index] + graph[index][j];
            }    
        }    
    }
}

 

五、图论大礼包

• 　　图论500题 http://blog.csdn.net/luomingjun12315/article/details/47438607