生成树 最小生成树_最小生成树

我就是我 2023-03-05 09:43 100阅读 0赞

生成树 最小生成树

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个整数NM。 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个以空格分隔的整数abw 。 其中, ab表示从顶点a到顶点b的边缘, w表示该边缘的权重。

Output:

输出:

Print the summation of edges weights in the MST.

在MST中打印边缘权重的总和。

Examples:

例子:

  1. INPUT:
  2. N = 4, M = 5
  3. 1 2 7
  4. 1 4 6
  5. 4 2 9
  6. 4 3 8
  7. 2 3 6
  8. OUTPUT:
  9. 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 ++实现:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. // edge structure for storing edge values.
  5. struct edge {
  6. ll a, b, w;
  7. };
  8. // declare arr with maximum size.
  9. edge arr[100005];
  10. // declare parent array.
  11. ll par[100005];
  12. // declare find function to find.
  13. // parent of current node.
  14. ll find(ll x)
  15. {
  16. // if par[x]==-1 then it is parent.
  17. if (par[x] == -1)
  18. return x;
  19. else
  20. return par[x] = find(par[x]); // path compression.
  21. }
  22. // declare comp function which will help.
  23. // to sort in according to min weight.
  24. bool comp(edge a, edge b)
  25. {
  26. if (a.w < b.w)
  27. return true;
  28. else
  29. return false;
  30. }
  31. // if a and b are with different then.
  32. // join them.
  33. void union1(ll a, ll b)
  34. {
  35. par[b] = a;
  36. }
  37. int main()
  38. {
  39. cout << "Enter N and M: ";
  40. ll n, m;
  41. cin >> n >> m;
  42. for (ll i = 1; i <= n; i++)
  43. par[i] = -1;
  44. cout << "Enter edge and weights:\n";
  45. for (ll i = 0; i < m; i++) {
  46. cin >> arr[i].a >> arr[i].b >> arr[i].w;
  47. }
  48. // initially sum variable as 0.
  49. ll sum = 0;
  50. // sort according to weight.
  51. sort(arr, arr + m, comp);
  52. for (ll i = 0; i < n; i++) {
  53. ll a = arr[i].a;
  54. ll b = arr[i].b;
  55. a = find(a);
  56. b = find(b);
  57. // check if they are already joined.
  58. if (a != b) {
  59. sum += arr[i].w;
  60. union1(a, b);
  61. }
  62. }
  63. cout << "Final sum: ";
  64. cout << sum << "\n";
  65. return 0;
  66. }

Output:

输出:

  1. Enter N and M: 4 5
  2. Enter edge and weights:
  3. 1 2 7
  4. 1 4 6
  5. 4 2 9
  6. 4 3 8
  7. 2 3 6
  8. 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

生成树 最小生成树

发表评论

表情:
评论列表 (有 0 条评论,100人围观)

还没有评论,来说两句吧...

相关阅读

    相关 生成

    最小生成树定义: 在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即![(u, v)\\in E][u_ v_in E]),而

    相关 生成

    一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 最小生成树在n个顶点的情形下,有n-1条边。生成树是对连

    相关 生成

    有n个城市,m条道路,现在输入n到m的道路的长度,用最少的边将图连接,输出让图连接的最小值 这道题我研究了好长时间才把答案看明白,现在给大家分享一下 具体代码如下

    相关 生成

    问题提出: 要在n个城市间建立通信联络网。顶点:表示城市,权:城市间通信线路的花费代价。希望此通信网花费代价最小。 问题分析: 答案只能从生成树中找,因为要做到任何

    相关 生成

    kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边。 p

    相关 生成

    最小生成树 什么是最小生成树 给定一张无向带权图G=(V,E,W),从中挑选出|V|-1条边,使得V中任意两点都有直接或者间接的路径 显然,最后得到的子