fork download
copy 
  1. // C++ program for Kruskal's algorithm to find Minimum
  2. // Spanning Tree of a given connected, undirected and
  3. // weighted graph
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // Creating shortcut for an integer pair
  8. typedef pair<int, int> iPair;
  9.  
  10. // Structure to represent a graph
  11. struct Graph
  12. {
  13. 	int V, E;
  14. 	vector< pair<int, iPair> > edges;
  15.  
  16. 	// Constructor
  17. 	Graph(int V, int E)
  18. 	{
  19. 		this->V = V;
  20. 		this->E = E;
  21. 	}
  22.  
  23. 	// Utility function to add an edge
  24. 	void addEdge(int u, int v, int w)
  25. 	{
  26. 		edges.push_back({w, {u, v}});
  27. 	}
  28.  
  29. 	// Function to find MST using Kruskal's
  30. 	// MST algorithm
  31. 	int kruskalMST();
  32. };
  33.  
  34. // To represent Disjoint Sets
  35. struct DisjointSets
  36. {
  37. 	int *parent, *rnk;
  38. 	int n;
  39.  
  40. 	// Constructor.
  41. 	DisjointSets(int n)
  42. 	{
  43. 		// Allocate memory
  44. 		this->n = n;
  45. 		parent = new int[n+1];
  46. 		rnk = new int[n+1];
  47.  
  48. 		// Initially, all vertices are in
  49. 		// different sets and have rank 0.
  50. 		for (int i = 0; i < n; i++)
  51. 		{
  52. 			rnk[i] = 0;
  53.  
  54. 			//every element is parent of itself
  55. 			parent[i] = i;
  56. 		}
  57. 	}
  58.  
  59. 	// Find the parent of a node 'u'
  60. 	// Path Compression
  61. 	int find(int u)
  62. 	{
  63. 		/* Make the parent of the nodes in the path
  64. 		from u--> parent[u] point to parent[u] */
  65. 		if (u != parent[u])
  66. 			parent[u] = find(parent[u]);
  67. 		return parent[u];
  68. 	}
  69.  
  70. 	// Union by rank
  71. 	void merge(int x, int y)
  72. 	{
  73. 		x = find(x), y = find(y);
  74.  
  75. 		/* Make tree with smaller height
  76. 		a subtree of the other tree */
  77. 		if (rnk[x] > rnk[y])
  78. 			parent[y] = x;
  79. 		else // If rnk[x] <= rnk[y]
  80. 			parent[x] = y;
  81.  
  82. 		if (rnk[x] == rnk[y])
  83. 			rnk[y]++;
  84. 	}
  85. };
  86.  
  87. /* Functions returns weight of the MST*/
  88.  
  89. int Graph::kruskalMST()
  90. {
  91. 	int mst_wt = 0; // Initialize result
  92.  
  93. 	// Sort edges in increasing order on basis of cost
  94. 	sort(edges.begin(), edges.end());
  95.  
  96. 	// Create disjoint sets
  97. 	DisjointSets ds(V);
  98.  
  99. 	// Iterate through all sorted edges
  100. 	vector< pair<int, iPair> >::iterator it;
  101. 	for (it=edges.begin(); it!=edges.end(); it++)
  102. 	{
  103. 		int u = it->second.first;
  104. 		int v = it->second.second;
  105. 		int set_u = ds.find(u);
  106. 		int set_v = ds.find(v);
  107. 		// Check if the selected edge is creating
  108. 		// a cycle or not (Cycle is created if u
  109. 		// and v belong to same set)
  110. 		if (set_u != set_v)
  111. 		{
  112. 			// Current edge will be in the MST
  113. 			// so print it
  114. 			cout << u << " - " << v << endl;
  115.  
  116. 			// Update MST weight
  117. 			mst_wt += it->first;
  118.  
  119. 			// Merge two sets
  120. 			ds.merge(set_u, set_v);
  121. 		}
  122. 	}
  123.  
  124. 	return mst_wt;
  125. }
  126.  
  127. // Driver program to test above functions
  128. int main()
  129. {
  130. 	/* Let us create above shown weighted
  131. 	and unidrected graph */
  132. 	int V = 9, E = 14;
  133. 	Graph g(V, E);
  134.  
  135. 	// making above shown graph
  136. 	g.addEdge(0, 1, 4);
  137. 	g.addEdge(0, 7, 8);
  138. 	g.addEdge(1, 2, 8);
  139. 	g.addEdge(1, 7, 11);
  140. 	g.addEdge(2, 3, 7);
  141. 	g.addEdge(2, 8, 2);
  142. 	g.addEdge(2, 5, 4);
  143. 	g.addEdge(3, 4, 9);
  144. 	g.addEdge(3, 5, 14);
  145. 	g.addEdge(4, 5, 10);
  146. 	g.addEdge(5, 6, 2);
  147. 	g.addEdge(6, 7, 1);
  148. 	g.addEdge(6, 8, 6);
  149. 	g.addEdge(7, 8, 7);
  150.  
  151. 	cout << "Edges of MST are \n";
  152. 	int mst_wt = g.kruskalMST();
  153.  
  154. 	cout << "\nWeight of MST is " << mst_wt;
  155.  
  156. 	return 0;
  157. }
  158.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Edges of MST are 
6 - 7
2 - 8
5 - 6
0 - 1
2 - 5
2 - 3
0 - 7
3 - 4

Weight of MST is 37
https://ideone.com/VJSZFV
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!