Kruskal 最小生成树（MST）算法
Prim算法是贪婪算法，类似于Kruskal算法。该算法始终从单个节点出发，经过多个相邻节点，以探索沿途所有连接的边。
该算法从一个空生成树开始。
其理念是维持两组顶点。第一组包含已包含在MST中的顶点，另一组包含尚未包含的顶点。
每一步，它都会考虑连接这两个集合的所有边，并从这些边中选择最小权重边。选定边后，将边的另一端点移动到包含MST的集合。
普里姆算法的工作原理
确定一个任意顶点作为MST的起始顶点。我们在上图中选择0。
按照步骤3到5，直到出现不包含在MST中的顶点（称为边缘顶点）。
找到连接任意树顶点与边缘顶点的边。
在这些边中找出最小值。
将选定的边添加到MST中。由于我们只考虑连接边缘顶点与其余边的边，因此从未得到一个环。
归还MST并离开
邻接矩阵表示的简单实现
按照上述步骤，利用上述Prim算法来求图的MST：
创建一个集合mstSet，跟踪MST中已包含的顶点。
为输入图中的所有顶点分配一个关键值。将所有键值初始化为无限。将第一个顶点的键值指定为0，这样它会被优先选中。
虽然mstSet不包含所有顶点
=> 选择一个mstSet 中不存在且有最小键值的顶点u。
=> 将u包含在mstSet中。
=> 更新 u 所有相邻顶点的键值。要更新键值，遍历所有相邻顶点。对于每个相邻顶点 v，如果边 u-v 的权重小于 v 的前一个键值，则将键值更新为 u-v 的权重。
使用关键值的目的是从切割中选择最小权重边。键值仅用于尚未包含在MST中的顶点，这些顶点的键值表示连接它们与MST中顶点集合的最小权重边。
import java.io.*; import java.lang.*; import java.util.*; class MST { // A utility function to find the vertex with minimum // key value, from the set of vertices not yet included // in MST int minKey(int key[], Boolean mstSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v < mstSet.length; v++) if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println("Edge \tWeight"); for (int i = 1; i < graph.length; i++) System.out.println(parent[i] + " - " + i + "\t" + graph[parent[i]][i]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { int V = graph.length; // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i < V; i++) { key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v < V; v++) // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); 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 } }; // Print the solution t.primMST(graph); } }输出
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
时间复杂度：O（V2由于我们使用邻接矩阵，如果输入图用邻接列表表示，那么借助二元堆，Prim算法的时间复杂度可以简化为O（（E+V） * logV）。辅助空间：O（V）
使用优先队列和邻接列表的高效实现
对于邻接列表表示，我们可以实现 O（（（E+V）*log（V）），因为我们可以在 O（V + E） 时间内找到每个顶点的所有相邻，并且在 O（Log V） 时间内通过优先队列获得最小值。
我们使用优先队列（最小堆）来始终选择权重最小的边。
将第一个顶点及其权重推入队列。
当队列不空时，提取最小权重边。
如果顶点未被访问，将其权重加到变量（res）上，并标记为已访问。
将该顶点所有未访问的相邻顶点推入队列。
处理完所有顶点后，返回以 res（分辨率）存储的总权重。
import java.util.PriorityQueue; import java.util.ArrayList; class GFG { // Returns total weight of the Minimum Spanning Tree static int spanningTree(int V, ArrayList<ArrayList<int[]>> adj) { // Min-heap storing {weight, vertex} PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); boolean[] visited = new boolean[V]; int res = 0; // Start from node 0 pq.add(new int[]{0, 0}); while(!pq.isEmpty()) { int[] p = pq.poll(); int wt = p[0]; int u = p[1]; if(visited[u]) continue; res += wt; visited[u] = true; // Push adjacent edges for(int[] v : adj.get(u)) { if(!visited[v[0]]) { pq.add(new int[]{v[1], v[0]}); } } } return res; } public static void main(String[] args) { int V = 3; ArrayList<ArrayList<int[]>> adj = new ArrayList<>(); for(int i = 0; i < V; i++) adj.add(new ArrayList<>()); adj.get(0).add(new int[]{1, 5}); adj.get(1).add(new int[]{0, 5}); adj.get(1).add(new int[]{2, 3}); adj.get(2).add(new int[]{1, 3}); adj.get(0).add(new int[]{2, 1}); adj.get(2).add(new int[]{0, 1}); System.out.println(spanningTree(V, adj)); } }输出
4
时间复杂度：O（（（E+V）*log（V）），其中V是顶点数，E是边数。
辅助空间：O（E+V），其中V是顶点数，E是边数
它是如何运作的？
核心基于MST的一个基本性质，称为割性质（如果我们将顶点划分为两组（即割），那么穿越该割的最轻边必须是图中某个MST的一部分。由于我们总是考虑割顶点，因此从不形成循环。
Prim算法的优缺点
优势：
Prim算法保证能在连通加权图中找到MST。
使用二元堆或斐波那契堆时，其时间复杂度为 O（（E+V）×log（V）），其中 E 是边数，V 是顶点数。
与其他一些MST算法相比，它是一个相对简单易懂和实现的算法。
缺点：
与Kruskal算法类似，Prim算法在多边密集图上可能较慢，因为它需要至少遍历所有边一次。
Prim算法依赖优先级队列，这会占用额外内存，并在非常大的图中使算法变慢。
起始节点的选择会影响MST输出，这在某些应用中可能并不理想。
编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548
