在图论中,寻找连通加权图的最小生成树(MST)是一个常见的问题。MST是图的边的子集,它连接了所有的顶点并最小化了总边权。解决这个问题的一种高效算法是Boruvka算法。
struct Edge { int src, dest, weight; }; // Define the structure to represent a subset for union-find struct Subset { int parent, rank; };
现在,让我们概述Boruvka算法中涉及的寻找最小生成树的步骤−
将 MST 初始化为空集。
为每个顶点创建一个子集,其中每个子集只包含一个顶点。
重复以下步骤,直到最小生成树(MST)有V-1条边(V是图中顶点的数量)−
对于每个子集,找到将其连接到另一个子集的最便宜的边。
将选定的边添加到最小生成树中。
对所选边的子集执行并集操作。
输出最小生成树。
在Boruvka算法中,有多种方法可以找到连接每个子集的最便宜的边。以下是两种常见的方法−
对于每个子集,遍历所有边,并找到将其连接到另一个子集的最小边。
跟踪选定的边并执行联合操作。
#include <iostream> #include <vector> #include <algorithm> struct Edge { int src, dest, weight; }; // Define the structure to represent a subset for union-find struct Subset { int parent, rank; }; // Function to find the subset of an element using path compression int find(Subset subsets[], int i) { if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // Function to perform union of two subsets using union by rank void unionSets(Subset subsets[], int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } // Function to find the minimum spanning tree using Boruvka's algorithm void boruvkaMST(std::vector<Edge>& edges, int V) { std::vector<Edge> selectedEdges; // Stores the edges of the MST Subset* subsets = new Subset[V]; int* cheapest = new int[V]; // Initialize subsets and cheapest arrays for (int v = 0; v < V; v++) { subsets[v].parent = v; subsets[v].rank = 0; cheapest[v] = -1; } int numTrees = V; int MSTWeight = 0; // Keep combining components until all components are in one tree while (numTrees > 1) { for (int i = 0; i < edges.size(); i++) { int set1 = find(subsets, edges[i].src); int set2 = find(subsets, edges[i].dest); if (set1 != set2) { if (cheapest[set1] == -1 || edges[cheapest[set1]].weight > edges[i].weight) cheapest[set1] = i; if (cheapest[set2] == -1 || edges[cheapest[set2]].weight > edges[i].weight) cheapest[set2] = i; } } for (int v = 0; v < V; v++) { if (cheapest[v] != -1) { int set1 = find(subsets, edges[cheapest[v]].src); int set2 = find(subsets, edges[cheapest[v]].dest); if (set1 != set2) { selectedEdges.push_back(edges[cheapest[v]]); MSTWeight += edges[cheapest[v]].weight; unionSets(subsets, set1, set2); numTrees--; } cheapest[v] = -1; } } } // Output the MST weight and edges std::cout << "Minimum Spanning Tree Weight: " << MSTWeight << std::endl; std::cout << "Selected Edges:" << std::endl; for (const auto& edge : selectedEdges) { std::cout << edge.src << " -- " << edge.dest << " \tWeight: " << edge.weight << std::endl; } delete[] subsets; delete[] cheapest; } int main() { // Pre-defined input for testing purposes int V = 6; int E = 9; std::vector<Edge> edges = { {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2}, {1, 4, 3}, {2, 3, 4}, {3, 4, 2}, {4, 5, 1}, {2, 5, 5} }; boruvkaMST(edges, V); return 0; }
Minimum Spanning Tree Weight: 9 Selected Edges: 0 -- 2 Weight: 3 1 -- 2 Weight: 1 1 -- 3 Weight: 2 4 -- 5 Weight: 1 3 -- 4 Weight: 2
我们首先定义两个结构 - Edge 和 Subset。 Edge 表示图中的一条边,包含边的源、目的地和权重。 Subset表示并查数据结构的子集,包含父级和排名信息。
find函数是一个辅助函数,它使用路径压缩来查找元素的子集。它递归地查找元素所属的子集的代表(父节点),并压缩路径以优化未来的查询。
unionSets函数是另一个辅助函数,使用按秩合并的方式对两个子集进行合并。它找到两个子集的代表,并根据秩进行合并,以保持平衡树。
boruvkaMST 函数采用边向量和顶点数 (V) 作为输入。它实现了 Boruvka 算法来查找 MST。
在 boruvkaMST 函数内,我们创建一个向量 selectedEdges 来存储 MST 的边。
我们创建一个Subset结构的数组来表示子集,并用默认值初始化它们。
我们还创建了一个数组 cheapest 来跟踪每个子集的最便宜的边。
变量 numTrees 被初始化为顶点的数量,MSTWeight 被初始化为 0。
该算法通过重复组合组件来进行,直到所有组件都在一棵树中。主循环运行直到 numTrees 变为 1。
在主循环的每次迭代中,我们迭代所有边并找到每个子集的最小加权边。如果边连接两个不同的子集,我们用最小加权边的索引更新最便宜的数组。
接下来,我们遍历所有的子集,如果一个子集存在最小权重的边,我们将其添加到selectedEdges向量中,更新MSTWeight,执行子集的并集操作,并减少numTrees的值。
最后,我们输出 MST 权重和选定的边。
主要功能提示用户输入顶点数和边数。然后,它获取每条边的输入(源、目标、权重)并使用输入调用 boruvkaMST 函数。
创建一个按照权重排序的优先队列来存储边。
对于每个子集,从优先级队列中找到将其连接到另一个子集的最小权重边。
跟踪选定的边并执行联合操作。
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; // Edge structure representing a weighted edge in the graph struct Edge { int destination; int weight; Edge(int dest, int w) : destination(dest), weight(w) {} }; // Function to find the shortest path using Dijkstra's algorithm vector<int> dijkstra(const vector<vector<Edge>>& graph, int source) { int numVertices = graph.size(); vector<int> dist(numVertices, INT_MAX); vector<bool> visited(numVertices, false); dist[source] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, source)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (visited[u]) { continue; } visited[u] = true; for (const Edge& edge : graph[u]) { int v = edge.destination; int weight = edge.weight; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); } } } return dist; } int main() { int numVertices = 4; vector<vector<Edge>> graph(numVertices); // Adding edges to the graph graph[0].push_back(Edge(1, 2)); graph[0].push_back(Edge(2, 5)); graph[1].push_back(Edge(2, 1)); graph[1].push_back(Edge(3, 7)); graph[2].push_back(Edge(3, 3)); int source = 0; vector<int> shortestDistances = dijkstra(graph, source); cout << "Shortest distances from source vertex " << source << ":\n"; for (int i = 0; i < numVertices; i++) { cout << "Vertex " << i << ": " << shortestDistances[i] << endl; } return 0; }
Shortest distances from source vertex 0: Vertex 0: 0 Vertex 1: 2 Vertex 2: 3 Vertex 3: 6
在这种方法中,我们使用优先队列来优化查找每个子集的最小加权边的过程。下面是代码的详细解释 −
代码结构和辅助函数(如find和unionSets)与之前的方法保持相同。
boruvkaMST 函数被修改为使用优先级队列来有效地找到每个子集的最小加权边。
而不是使用最便宜的数组,我们现在创建一个边的优先队列(pq)。我们用图的边来初始化它。
主循环运行直到 numTrees 变为 1,与之前的方法类似。
在每次迭代中,我们从优先队列中提取最小权重的边(minEdge)。
然后我们使用find函数找到minEdge的源和目标所属的子集。
如果子集不同,我们将minEdge添加到selectedEdges向量中,更新MSTWeight,执行子集的合并,并减少numTrees。
该过程将继续,直到所有组件都在一棵树中。
最后,我们输出 MST 权重和选定的边。
主要功能与之前的方法相同,我们有预定义的输入用于测试目的。
Boruvka 算法为查找加权图的最小生成树提供了一种有效的解决方案。在用 C++ 实现该算法时,我们的团队深入探索了两种不同的路径:一种是传统的或“朴素”的方法。另一个利用优先级队列。取决于当前给定问题的具体要求。每种方法都有一定的优点,可以相应地实施。通过理解和实现 Boruvka 算法,您可以有效地解决 C++ 项目中的最小生成树问题。
以上就是C++中的Boruvka算法用于最小生成树的详细内容,更多请关注php中文网其它相关文章!
已抢66234个
抢已抢35393个
抢已抢19634个
抢