05-最小生成树算法

实现一个最小生成树算法，并分析其时间复杂度和空间复杂度。

public int prim(int[][] graph) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;
    int res = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;
        res += dist[u];
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return res;
}

最小生成树（Minimum Spanning Tree，MST）是一种图论问题，其目的是找到一个无向图的生成树，使得树上所有边的权值之和最小。最小生成树算法有多种，其中较为常见的有Prim算法和Kruskal算法。

以下是Prim算法的实现步骤：

1. 选择任意一个顶点作为起点，将其加入生成树中。
2. 对于所有与生成树中顶点相邻的边，选择其中权值最小的边，将其连接的顶点加入生成树中。
3. 重复步骤2，直到生成树包含了所有顶点。

时间复杂度分析：该算法的时间复杂度为O(n^2)，其中n为顶点数。因为需要遍历n次所有顶点，每次需要找到当前未访问的顶点中dist值最小的顶点，需要O(n)的时间，同时需要更新与该顶点相邻的所有顶点的dist值，需要O(n)的时间，所以总共需要O(n^2)的时间。

空间复杂度分析：该算法的空间复杂度为O(n)，其中n为顶点数。因为需要维护visited数组和dist数组，大小都为n。

验证：

public static void main(String[] args) {
    int[][] graph = new int[][] {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0}
    };
    int res = LeastGenTree.prim(graph);
    //最小生成树的权值和为：16
    System.out.println("最小生成树的权值和为：" + res);
}

其中，graph是一个邻接矩阵表示的无向图，这里以一个5个顶点的例子进行演示。最后输出的结果为最小生成树的权值和。

需要注意的是，这里的graph是一个完全图，即所有顶点之间都有边相连。如果输入的图不是完全图，需要先进行处理，将没有边相连的顶点之间的边权设置为0。