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

时间:2022-02-12 21:34:08

一、主要内容:

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

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

题目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,直到所有的顶点都进入了生成树为止,此时的生成树就是最小生成树.

 

最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)
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;    
}
Prime 算法

 kruskal算法的基本思想:

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

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

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

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

最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)
#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;
}
kruskal 算法

四、最短路径算法

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

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

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

  

最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)
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的最短路径 
                }     
            }    
        }    
    }    
}
Floyd 算法

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

最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)最小生成树(prime算法 & kruskal算法)和 最短路径算法(floyd算法 & dijkstra算法)
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];
            }    
        }    
    }
}
dijkstra 算法

 

五、图论大礼包