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

清疚 2022-06-12 05:29 163阅读 0赞

带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法；有向图的最短路径算法有dijkstra算法和floyd算法。

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

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

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

prime算法的基本思想

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

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

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

int prime(int cur)
    {
        
        int index;
        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;    
    }

![复制代码][copycode.gif]

kruskal算法：构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树的根节点，则它是一个含有n棵树的森林 。之后，从网的边集中选取一条权值最小的边，若该边的两个顶点分属不同的树 ，则将其加入子图，也就是这两个顶点分别所在的 两棵树合成一棵树；反之，若该边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林只有一棵树。kruskal算法能够在并查集的基础很快的实现。结合例子来介绍具体算法实现（其中并查集的部分可以详见并查集介绍部分） http://poj.org/problem?id=1251

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int size = 128; 
    int n;
    int father[size];
    int rank[size];
    
    //把每条边成为一个结构体，包括起点、终点和权值 
    typedef struct node
    {
        
        int val;
        int start;
        int end;    
    }edge[SIZE * SIZE / 2];
    
    //把每个元素初始化为一个集合 
    void make_set()
    {
        
        for(int i = 0; i < n; i ++){
        
            father[i] = i;
            rank[i] = 1;    
        }    
        return ;
    }
    
    //查找一个元素所在的集合,即找到祖先 
    int find_set(int x)
    {
        
        if(x != father[x]){
        
            father[x] = find_set(father[x]);    
        }    
        return father[x];
    }
    
    //合并x,y所在的两个集合：利用Find_Set找到其中两个
    //集合的祖先，将一个集合的祖先指向另一个集合的祖先。
    void Union(int x, int y)
    {
        
        x = find_set(x);    
        y = find_set(y);
        if(x == y){
        
            return ;    
        }
        if(rank[x] < rank[y]){
        
            father[x] = find_set(y);    
        }
        else{
        
            if(rank[x] == rank[y]){
        
                rank[x] ++;    
            }    
            father[y] = find_set(x);
        }
        return ;
    }
    
    bool cmp(pnode a, pnode b)
    {
        
        return a.val < b.val;    
    }
    
    int kruskal(int n) //n为边的数量 
    {
        
        int sum = 0;
        make_set();
        for(int i = 0; i < n; i ++){   //从权最小的边开始加进图中 
            if(find_set(edge[i].start) != find_set(edge[i].end)){
        
                Union(edge[i].start, edge[i].end);
                sum += edge[i].val;    
            }    
        }
        return sum;    
    }
    
    int main()
    {
        
        while(1){
        
            scanf("%d", &n);    
            if(n == 0){
        
                break;    
            }
            char x, y;
            int m, weight;
            int cnt = 0;
            for(int i = 0; i < n - 1; i ++){
        
                cin >> x >> m; 
                //scanf("%c %d", &x, &m);    
                //printf("%c %d ", x, m);
                for(int j = 0; j < m; j ++){
        
                    cin >> y >> weight; 
                    //scanf("%c %d", &y, &weight);
                    //printf("%c %d ", y, weight);    
                    edge[cnt].start = x - 'A';
                    edge[cnt].end = y - 'A';
                    edge[cnt].val = weight;
                    cnt ++;
                }
            }
            
            sort(edge, edge + cnt, cmp); //对边按权从小到大排序 
            cout << kruskal(cnt) << endl; 
        }    
    }

![复制代码][copycode.gif]

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

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

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的最短路径 
                    }     
                }    
            }    
        }    
    }

![复制代码][copycode.gif]

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

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];
                }    
            }    
        }
    }

![复制代码][copycode.gif]

[ExpandedBlockStart.gif]: /images/20220612/269f60fc17044303ba02364293ec7066.png
[copycode.gif]: /images/20220612/36ddfc8e3fd848e99d4c515070dec99c.png