最小生成树一般有Prim算法和Dijkstra算法。小编就详细的介绍这两种算法。

普里姆（Prim）算法

Prim算法是用于生成无向带权连通图的最小生成树(MST)的一种算法, 并且可以解决边权值为负的情况. Prim算法从任意一顶点x开始, 初始化V'=x, 每次采取贪心策略选取跨越V与V-V'的最小边, 扩大现有的子树V', 直到遍历了图中所有的顶点.

算法流程

从以上分析可以知道, Prim算法与Dijkstra算法的求解思路一致, 但是在Dijkstra算法中, dist数组维护了当前顶点到源点node的最短距离; 而在Prim算法中, dist维护了当前顶点到当前生成树的距离.

1. 初始化dist数组为INF, 访问数组vis为false.

2.选定任意一个节点node, 标记vis[node]=true, dist[node]=0

3. 找出所有未访问过的点中的距离最小的点u, 标记vis[u]=true, 将最后一次松弛的边加入生成树

4. 以u作为中间点, 访问其所有邻边进行松弛, 被松弛的点v记录下(u,v)边

5. 循环|V|-1次

算法模板:

void prim() {
    memset(vis,0x00,sizeof vis);
    for(int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[1] = 0;
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        int node = -1;
        for(int j = 1; j <= n; ++j) {
            if(!vis[j] && (node == -1 || dist[j] > dist[node])) {
                node = j;
            }
            if(node==-1) break;
            vis[node] = true;
            ans += dist[node];
            for (int j = 1; j <= n; ++j) {
                dist[j] = min(dist[j], g[node][j]);
            }
       }
    }
}

时间复杂度

Prim算法循环|V|-1次, 使用线性扫描算法寻找最小值的时间复杂度为O(|V|^2+|E|), 使用堆优化版Prim算法的时间复杂度是O(|E|log|V|).

克鲁斯卡尔（Kruskal）算法

算法流程：

1. 将图G中每个顶点看做独立的连通分量.
2. 将所有边按照权值从小到大排序加入集合S
3. 从S中取出一条权值最小的边(u, v), 如果u和v不在同一个连通分量中, 合并u和v所在的连通分量, 同时将(u, v)加入生成树的边集合E'
4. 重复(3)直到所有节点在一个连通分量中, 边集合E'就是MST.

算法模板：

public class prim {
    static int N = 9; // 图中边的数量
    static int P = 6; // 图中顶点的数量
    //构建表示路径的类
    public static class edge implements Comparable<edge>{
        //每个路径都有 2 个顶点和 1 个权值
        int initial;
        int end;
        int weight;
        public edge(int initial, int end, int weight) {
            this.initial = initial;
            this.end = end;
            this.weight = weight;
        }
        //对每个 edge 对象根据权值做升序排序
        @Override
        public int compareTo(edge o) {
            return this.weight - o.weight;
        }
    }
  
    public static void kruskal_MinTree(edge[] edges,edge [] minTree) {
        int []assists = new int[P];
        //每个顶点配置一个不同的标记值
        for (int i = 0; i < P; i++) {
            assists[i] = i;
        }
        //根据权值，对所有边进行升序排序
        Arrays.sort(edges);
        //遍历所有的边
        int num = 0;
        for (int i = 0; i < N; i++) {
            //找到当前边的两个顶点在 assists 数组中的位置下标
            int initial = edges[i].initial - 1;
            int end = edges[i].end - 1;
            //如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
            if (assists[initial] != assists[end]) {
                //记录该边，作为最小生成树的组成部分
                minTree[num] = edges[i];
                //计数+1
                num++;
                int elem = assists[end];
                //将新加入生成树的顶点标记全不更改为一样的
                for (int k = 0; k < P; k++) {
                    if (assists[k] == elem) {
                        assists[k] = assists[initial];
                    }
                }
                //如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环
                if (num == P - 1) {
                    break;
                }
            }
        }
    }
    public static void display(edge [] minTree) {
        System.out.println("最小生成树为：");
        int cost = 0;
        for (int i = 0; i < P - 1; i++) {
            System.out.println(minTree[i].initial+" - "+ minTree[i].end+" 权值为："+minTree[i].weight);
            cost += minTree[i].weight;
        }
        System.out.print("总权值为:"+cost);
    }
  
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        edge[] edges = new edge[N];
        edge[] minTree = new edge[P-1];
        System.out.println("请输入图中各个边的信息：");
        for(int i=0;i<N;i++) {
            int initial = scn.nextInt(), end = scn.nextInt(), weight = scn.nextInt();
            edges[i] = new edge(initial,end,weight);
        }
        kruskal_MinTree(edges,minTree);
        display(minTree);
    }
}

总结

稀疏图一般选择 prim,采用 邻接矩阵 进行存储边之间的关系。

稠密图一般选择 Kruskal ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。