最小生成树一般有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）算法

算法流程：

将图G中每个顶点看做独立的连通分量.将所有边按照权值从小到大排序加入集合S从S中取出一条权值最小的边(u, v), 如果u和v不在同一个连通分量中, 合并u和v所在的连通分量, 同时将(u, v)加入生成树的边集合E'重复(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 ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。