企业官网建设流程全解析

相关网站查询,网站建设费 无形资产,wordpress主题缩略图,最新互联网项目平台网站Kruskal 最小生成树#xff08;MST#xff09;算法Prim算法是贪婪算法#xff0c;类似于Kruskal算法。该算法始终从单个节点出发#xff0c;经过多个相邻节点#xff0c;以探索沿途所有连接的边。该算法从一个空生成树开始。 其理念是维持两组顶点。第一组包含已包含在MST…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 Weight0 - 1 21 - 2 30 - 3 61 - 4 5时间复杂度OV2由于我们使用邻接矩阵如果输入图用邻接列表表示那么借助二元堆Prim算法的时间复杂度可以简化为OEV * logV。辅助空间OV使用优先队列和邻接列表的高效实现对于邻接列表表示我们可以实现 OEV*logV因为我们可以在 OV E 时间内找到每个顶点的所有相邻并且在 OLog 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, ArrayListArrayListint[] adj) { // Min-heap storing {weight, vertex} PriorityQueueint[] 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; ArrayListArrayListint[] 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时间复杂度OEV*logV其中V是顶点数E是边数。辅助空间OEV其中V是顶点数E是边数它是如何运作的核心基于MST的一个基本性质称为割性质如果我们将顶点划分为两组即割那么穿越该割的最轻边必须是图中某个MST的一部分。由于我们总是考虑割顶点因此从不形成循环。Prim算法的优缺点优势Prim算法保证能在连通加权图中找到MST。使用二元堆或斐波那契堆时其时间复杂度为 OEV×logV其中 E 是边数V 是顶点数。与其他一些MST算法相比它是一个相对简单易懂和实现的算法。缺点与Kruskal算法类似Prim算法在多边密集图上可能较慢因为它需要至少遍历所有边一次。Prim算法依赖优先级队列这会占用额外内存并在非常大的图中使算法变慢。起始节点的选择会影响MST输出这在某些应用中可能并不理想。编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548