贪婪算法在求解最小生成树中的应用（JAVA）--Prim算法

贪婪算法：通过一系列步骤来构造问题的解，每一步对目前构造的部分分解做一个拓展，直到获得问题的完整解为止,而算法的核心思想就在于，算法的每一步都必须满足以下条件：可行（满足问题的约束条件）、局部最优（当前步骤所有可行选择中的局部最优解）、不可取消（一旦选择，在后续步骤中不可改变）。

对于连通图来说生成树定义为包含图中所有顶点的连通无环子图

而在加权连通图中权重最小的生成树被称为最小生成树

Prim算法被又称为“加点法”,我们从图中的顶点集合中任意选择一个顶点作为序列的初始子树，每次迭代的时候，以贪婪的方式扩张生成树，该算法每次只扩展一个点，迭代的总次数为n-1。所以这就要求对于每个不在树中的顶点，必须知道它连接树中顶点的最短边信息。我们可以给一个顶点附加两个标记：树中最近顶点的名称以及对应边的长度。对于任意加入生成树中的顶点来说，我们要做两步，操作一：将该顶点从集合V-Vt 移动带顶点集合Vt中，操作二：对V-Vt中的每个顶点更新。

我们以下面这个图为例子讲解Prim算法的过程：

Input:

6 10
1 2 3
1 5 6
1 6 5
2 6 5
2 3 1
3 6 4
3 4 6
4 6 5
4 5 8

5 6 2

Output:

15

完整代码如下：

import java.util.Scanner;

public class Main {
    static int[][] e = new int[7][7];
    static int[] book = new int[7];
    static int[] dis = new int[7];
    static int count = 0;
    static int sum = 0;
    static int n, m;
    static int min, mark;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = 99999999;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            e[a][b] = c;
            e[b][a] = c;
        }
        for (int i = 1; i <= n; i++) {
            dis[i] = e[1][i];
        }
        book[1] = 1;

        prime();

        System.out.println(sum);
    }

    private static void prim() {
        count++;
        while (count < n) {
            min = 99999999;
            for (int i = 1; i <= n; i++) {
                if (book[i] == 0 && dis[i] < min) {
                    min = dis[i];
                    mark = i;
                }
            }
            book[mark] = 1;
            count++;
            sum += dis[mark];
            for (int i = 1; i <= n; i++) {
                if (book[i] == 0 && dis[i] > e[mark][i]) {
                    dis[i] = e[mark][i];
                }
            }
        }
    }
}

时间复杂度O(n^2)，如果采用堆来构造一个优先队列则会使算法的时间复杂度变为O(nlogn)

很感兴趣的读者可以参考图论算法（四）--最小生成树的Kruskal [ 加边 ] 、Prim [ 加点 ] 的解法（JAVA）这篇文章