生成树 最小生成树_最小生成树
生成树 最小生成树
Problem statement:
问题陈述:
Given a weighted undirected graph. Find the sum of weights of edges of a Minimum Spanning Tree.
给定加权无向图。 查找最小生成树边缘的权重总和。
Input:
输入:
Given 2 integers N and M. N represents the number of vertices in the graph. M represents the number of edges between any 2 vertices.
给定2个整数N和M。 N表示图中的顶点数。 M表示任意2个顶点之间的边数。
Then M lines follow, each line has 3 space-separated integers a, b, w. Where, a and b represents an edge from a vertex a to a vertex b and w represents the weight of that edge.
然后跟随M行,每行具有3个以空格分隔的整数a , b , w 。 其中, a和b表示从顶点a到顶点b的边缘, w表示该边缘的权重。
Output:
输出:
Print the summation of edges weights in the MST.
在MST中打印边缘权重的总和。
Examples:
例子:
INPUT:
N = 4, M = 5
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6
OUTPUT:
19, is the sum of edges of MST.
Solution Approach
解决方法
The problem can be solved with the help of Kruskal and Prim’s Algorithm of the minimum spanning tree.
该问题可以借助最小生成树的Kruskal和Prim算法来解决。
Kruskal Algorithm: Kruskal’s algorithm follows the greedy approach in each iteration it adds the weight of the minimum edge to a growing spanning tree.
Kruskal算法:Kruskal算法在每次迭代中都遵循贪婪方法,它将最小边缘的权重添加到增长的生成树上。
Following steps are used in Kruskal algo,
在Kruskal算法中使用以下步骤,
Sort the graph edges on the basis of their weight.
根据权重对图形边缘进行排序。
Add only those edge which doesn’t form cycle from minimum weight to maximum edge weight.
仅添加那些不会形成从最小重量到最大边缘重量的循环的边缘。
C++ Implementation:
C ++实现:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// edge structure for storing edge values.
struct edge {
ll a, b, w;
};
// declare arr with maximum size.
edge arr[100005];
// declare parent array.
ll par[100005];
// declare find function to find.
// parent of current node.
ll find(ll x)
{
// if par[x]==-1 then it is parent.
if (par[x] == -1)
return x;
else
return par[x] = find(par[x]); // path compression.
}
// declare comp function which will help.
// to sort in according to min weight.
bool comp(edge a, edge b)
{
if (a.w < b.w)
return true;
else
return false;
}
// if a and b are with different then.
// join them.
void union1(ll a, ll b)
{
par[b] = a;
}
int main()
{
cout << "Enter N and M: ";
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++)
par[i] = -1;
cout << "Enter edge and weights:\n";
for (ll i = 0; i < m; i++) {
cin >> arr[i].a >> arr[i].b >> arr[i].w;
}
// initially sum variable as 0.
ll sum = 0;
// sort according to weight.
sort(arr, arr + m, comp);
for (ll i = 0; i < n; i++) {
ll a = arr[i].a;
ll b = arr[i].b;
a = find(a);
b = find(b);
// check if they are already joined.
if (a != b) {
sum += arr[i].w;
union1(a, b);
}
}
cout << "Final sum: ";
cout << sum << "\n";
return 0;
}
Output:
输出:
Enter N and M: 4 5
Enter edge and weights:
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6
Final sum: 19
Time Complexity in worst case is: (nlog(n))
最坏情况下的时间复杂度是: (nlog(n))
Space Complexity in worst case is: O(n)
最坏情况下的空间复杂度是: O(n)
Problem reference: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/practice-problems/algorithm/minimum-spanning-tree-5/
问题参考:https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/practice-problems/algorithm/minimum-spanning-tree-5/
翻译自: https://www.includehelp.com/icp/minimum-spanning-tree.aspx
生成树 最小生成树
还没有评论,来说两句吧...