赞
踩
最小生成树算法是求加权连通图的一种算法,它可以找出一个连通子图,使得子图中所有边的权值之和最小。最小生成树算法的主要应用是在网络设计、公路规划、电力管网规划等领域。
算法步骤:
首先选定任意一个结点作为起点,将该结点加入生成树中。
查找与已加入生成树中结点最近的未加入的结点,将该结点和与其相连的边加入到生成树中。
重复步骤2,直到所有结点均已加入生成树中为止。
算法实现:
最小生成树算法的实现方法有多种,其中比较常见的有Prim算法和Kruskal算法。
Prim算法从一个任意选定的起点开始,将该点加入生成树中,同时将该点能到达的所有点的边都加入到一个集合中。然后在这个集合中选择权值最小的边所连接的点,将该点加入生成树中,并将该点能到达的所有点的边都加入到集合中。以此类推,直到所有点都加入到生成树中。
Kruskal算法先将所有的边按权值从小到大排序,然后从小到大依次选择每一条边。如果这条边的两个端点已经在同一个集合中,则该边不会加入到生成树中;否则将该边加入到集合中,并将这两个端点所在的集合合并成一个集合。重复此操作,直到所有点都加入到生成树中。
无论是Prim算法还是Kruskal算法,都可以在O(E log V)的时间内求出最小生成树。其中,E为边的数量,V为结点的数量。
最小生成树(Minimum Spanning Tree,简称 MST)是求一个带权无向连通图的所有生成树中,边的权值和最小的一棵生成树。常用的算法有Prim算法和Kruskal算法。
下面是 C 语言实现 Prim 算法的代码及详细注释。
#include<stdio.h> #include<stdlib.h> #include<limits.h> #define MAX_VERTEX_NUM 1000 // 图的最大顶点数 #define INF INT_MAX // 定义正无穷 typedef struct{ int numVertex; // 顶点数目 int numEdge; // 边的数目 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,存储边的权重 }Graph; void Prim(Graph *G){ int lowcost[MAX_VERTEX_NUM]; // 从V中某个点出发到其他点的最小距离集合 int closest[MAX_VERTEX_NUM]; // 记录最小距离点的编号 int visited[MAX_VERTEX_NUM]; // 顶点是否被访问的标记 int i, j, k, min; // 初始化 visited 数组,最开始都为未访问 for(i = 0; i < G->numVertex; i++) visited[i] = 0; // 初始化距离数组和 closest 数组,从顶点 0 出发到其他点的距离 for(i = 1; i < G->numVertex; i++){ lowcost[i] = G->edge[0][i]; closest[i] = 0; } visited[0] = 1; // 从 0 号点开始 for(i = 1; i < G->numVertex; i++){ min = INF; // 找到到其他点最近的点(最小权值),同时标记为已访问 for(j = 1; j < G->numVertex; j++){ if(!visited[j] && lowcost[j] < min){ min = lowcost[j]; k = j; // 记录最小的边所连的顶点编号 } } visited[k] = 1; // 标记顶点为已访问 // 更新从V中某个点出发到其他点的最小距离集合和 closest 数组 for(j = 1; j < G->numVertex; j++){ if(!visited[j] && G->edge[k][j] < lowcost[j]){ lowcost[j] = G->edge[k][j]; closest[j] = k; } } } // 输出最小生成树 int sum = 0; // 总权值 for(i = 1; i < G->numVertex; i++){ printf("%d - %d: %d\n", closest[i], i, G->edge[closest[i]][i]); sum += G->edge[closest[i]][i]; // 累加边的权值 } printf("总权值: %d\n", sum); } int main(){ Graph G; // 输入图的顶点数和边的数目 printf("请输入图的顶点数和边的数目: "); scanf("%d%d", &G.numVertex, &G.numEdge); // 输入图的边的信息 for(int i = 0; i < G.numVertex; i++){ for(int j = 0; j < G.numVertex; j++){ G.edge[i][j] = INF; } } printf("请依次输入每条边所连的两个顶点和边的权值:\n"); for(int i = 0; i < G.numEdge; i++){ int u, v, w; scanf("%d%d%d", &u, &v, &w); G.edge[u][v] = G.edge[v][u] = w; } Prim(&G); // 调用 Prim 算法求解最小生成树 return 0; }
主要涉及的算法流程:
代码中定义的 INF 表示正无穷,即两个点之间没有直接连通的边,用来表示它们之间的距离无穷大。
Prim 算法与 Dijkstra 算法有很多相似之处,两者的区别在于目标不同:Dijkstra 算法是求从起点到其他所有点的最短路径,而 Prim 算法是求一颗最小生成树。
最小生成树算法是图论中的经典问题,它的目标是在给定的带权连通图中找到一棵生成树,使得这棵生成树的总权值最小。常见的最小生成树算法有 Prim 算法和 Kruskal 算法。
本文将详细介绍 Prim 算法和 Kruskal 算法的实现方法,并提供 C++ 代码。
Prim 算法是一种贪心算法,它是从一个顶点开始不断扩展生成树的边,直到生成一棵包含所有顶点的树。具体实现中,Prim 算法使用了一个优先队列来管理候选的边,每次从队列中选择权值最小的边加入生成树。
以下是 Prim 算法的 C++ 代码实现:
#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAXN = 1000; // 最大顶点数 const int INF = 0x3f3f3f3f; // 无穷大 struct Edge { int u, v, w; Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {} bool operator<(const Edge& e) const { // 用于优先队列的比较运算符 return w > e.w; } }; vector<Edge> edges[MAXN]; // 存边 bool visited[MAXN]; // 记录顶点是否已经在生成树中 int dist[MAXN]; // 记录生成树到每个顶点的最短距离 int parent[MAXN]; // 记录生成树中每个顶点的父节点 void prim(int s, int n) { // s 表示起点,n 表示顶点数 priority_queue<Edge> pq; // 定义优先队列 memset(dist, INF, sizeof(dist)); // 初始化距离数组 memset(visited, false, sizeof(visited)); // 初始化访问记录数组 memset(parent, -1, sizeof(parent)); // 初始化父节点数组 dist[s] = 0; // 初始化起点的距离为 0 pq.push(Edge(-1, s, 0)); // 将起点加入优先队列 while (!pq.empty()) { int u = pq.top().v; pq.pop(); if (visited[u]) continue; visited[u] = true; for (auto& e : edges[u]) { // 遍历 u 的所有邻接边 int v = (e.u == u ? e.v : e.u); if (!visited[v] && dist[v] > e.w) { // 如果 v 未访问过且经过 u 到达 v 比原始距离更优 dist[v] = e.w; parent[v] = u; pq.push(e); } } } } int main() { int n, m; cin >> n >> m; // 输入顶点数和边数 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; // 输入一条边 edges[u].push_back(Edge(u, v, w)); // 存储边 edges[v].push_back(Edge(v, u, w)); } prim(1, n); // 假设从节点 1 开始构建生成树 for (int i = 1; i <= n; i++) { cout << i << " " << parent[i] << endl; // 输出每个节点的父节点 } return 0; }
Kruskal 算法也是一种贪心算法,它首先将所有边按照权值从小到大排序,然后依次从小到大加入边,直到生成一棵包含所有顶点的树为止。具体实现中,Kruskal 算法使用了并查集来维护连通性。
以下是 Kruskal 算法的 C++ 代码实现:
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int MAXN = 1000; // 最大顶点数 const int INF = 0x3f3f3f3f; // 无穷大 struct Edge { int u, v, w; Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {} bool operator<(const Edge& e) const { // 用于排序的比较运算符 return w < e.w; } }; vector<Edge> edges; // 存边 int parent[MAXN]; // 记录每个节点所在的集合 int find(int x) { // 查找 x 所在的集合 if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; edges.push_back(Edge(u, v, w)); // 存储边 } sort(edges.begin(), edges.end()); // 排序 int cnt = 0; // 记录已经选取的边数 int ans = 0; // 记录生成树的总权值 for (int i = 1; i <= n; i++) { parent[i] = i; // 初始化每个节点所在的集合 } for (auto& e : edges) { // 遍历所有边 int u = e.u, v = e.v, w = e.w; int pu = find(u), pv = find(v); if (pu != pv) { // 如果 u 和 v 不在同一个集合中 parent[pu] = pv; // 合并集合 ans += w; // 更新生成树的总权值 cnt++; if (cnt == n - 1) break; // 已经选取了 n - 1 条边,可以退出循环 } } cout << ans << endl; // 输出生成树的总权值 return 0; }
以上就是 Prim 算法和 Kruskal 算法的 C++ 代码实现及详解。
最小生成树算法是一个经典的图论问题,主要解决的是一个无向图中连接所有顶点的问题,但是连接的边的权值和必须达到最小。常见的最小生成树算法有 Prim 算法和 Kruskal 算法。本文将介绍如何使用 Java 语言实现 Prim 算法和 Kruskal 算法,以及代码详解。
Prim 算法是一个贪心算法,它的基本思想是从一个顶点开始,不断地选择与当前已选定的顶点相连且具有最小边权值的顶点,直到所有顶点都被选定。具体实现步骤如下:
下面是 Prim 算法的 Java 实现代码:
public class Prim { /** * 使用邻接矩阵表示图 * @param graph * @param start * @return */ public static List<Edge> prim(int[][] graph, int start) { int n = graph.length; // 图的节点个数 boolean[] visited = new boolean[n]; // 用于记录每个节点是否被访问过 List<Edge> edges = new ArrayList<>(); // 用于存储最小生成树的边 // 将起点标记为已访问 visited[start] = true; // 从起点开始,不断选择与当前已选定的顶点相连且具有最小边权值的顶点 while (edges.size() < n - 1) { int minWeight = Integer.MAX_VALUE; // 记录当前最小边权值 Edge minEdge = null; // 记录当前最小边 for (int i = 0; i < n; i++) { if (visited[i]) { for (int j = 0; j < n; j++) { if (!visited[j] && graph[i][j] > 0 && graph[i][j] < minWeight) { minWeight = graph[i][j]; minEdge = new Edge(i, j, minWeight); } } } } // 将当前最小边的另一个节点加入到集合中,并标记为已访问 visited[minEdge.to] = true; edges.add(minEdge); } return edges; } /** * 表示一条边 */ static class Edge { int from; int to; int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } @Override public String toString() { return "(" + from + ", " + to + ", " + weight + ")"; } } public static void main(String[] args) { int[][] graph = { {0, 7, 0, 5, 0, 0, 0}, {7, 0, 8, 9, 7, 0, 0}, {0, 8, 0, 0, 5, 0, 0}, {5, 9, 0, 0, 15, 6, 0}, {0, 7, 5, 15, 0, 8, 9}, {0, 0, 0, 6, 8, 0, 11}, {0, 0, 0, 0, 9, 11, 0} }; List<Edge> edges = prim(graph, 0); for (Edge edge : edges) { System.out.println(edge); } } }
Kruskal 算法也是一个贪心算法,它的基本思想是先将图中所有的边按照权值从小到大排序,然后依次选择每条边,将其加入到最小生成树中,直到所有的节点都被连接。具体实现步骤如下:
下面是 Kruskal 算法的 Java 实现代码:
public class Kruskal { /** * 使用邻接矩阵表示图 * @param graph * @return */ public static List<Edge> kruskal(int[][] graph) { int n = graph.length; // 图的节点个数 List<Edge> edges = new ArrayList<>(); // 用于存储最小生成树的边 // 将所有边按照权值从小到大排序 PriorityQueue<Edge> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight)); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (graph[i][j] > 0) { heap.offer(new Edge(i, j, graph[i][j])); } } } // 初始化并查集 int[] parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } // 依次选择每条边,如果边的两个端点不在同一个连通分量中,则将其加入到最小生成树中 while (edges.size() < n - 1 && !heap.isEmpty()) { Edge edge = heap.poll(); int from = edge.from; int to = edge.to; int weight = edge.weight; if (find(parent, from) != find(parent, to)) { union(parent, from, to); edges.add(edge); } } return edges; } /** * 查找节点所在的集合 * @param parent * @param node * @return */ private static int find(int[] parent, int node) { while (node != parent[node]) { parent[node] = parent[parent[node]]; node = parent[node]; } return node; } /** * 合并两个集合 * @param parent * @param x * @param y */ private static void union(int[] parent, int x, int y) { int rootX = find(parent, x); int rootY = find(parent, y); if (rootX != rootY) { parent[rootX] = rootY; } } /** * 表示一条边 */ static class Edge { int from; int to; int weight; public Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } @Override public String toString() { return "(" + from + ", " + to + ", " + weight + ")"; } } public static void main(String[] args) { int[][] graph = { {0, 7, 0, 5, 0, 0, 0}, {7, 0, 8, 9, 7, 0, 0}, {0, 8, 0, 0, 5, 0, 0}, {5, 9, 0, 0, 15, 6, 0}, {0, 7, 5, 15, 0, 8, 9}, {0, 0, 0, 6, 8, 0, 11}, {0, 0, 0, 0, 9, 11, 0} }; List<Edge> edges = kruskal(graph); for (Edge edge : edges) { System.out.println(edge); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。