fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph{ 
  5. public: 
  6. 	int n;
  7. 	int m; 
  8. 	int maxEdges;
  9. 	bool isDirected;
  10.  
  11. 	vector<vector<int>> adj;
  12. 	vector<pair<int, pair<int, int>>> weights;
  13.  
  14. 	Graph(int nodes, bool isDiGraph) : adj(nodes){ 
  15. 		n = nodes;
  16. 		m = 0;
  17. 		isDirected = isDiGraph; 
  18. 		maxEdges = isDirected ? n*(n-1) : n*(n-1)/2;
  19. 	}
  20.  
  21. 	void insertEdge(int u, int v, int weight){ 
  22.  
  23. 		if(u >= n || v >=n || u < 0 || v < 0){ 
  24. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  25. 			return;
  26. 		}
  27.  
  28. 		if(m == maxEdges){ 
  29. 			cout<<"Maximum allowed edges are already in the graph. Can't insert more.\n";
  30. 			return; 
  31. 		}
  32.  
  33. 		weights.push_back({weight, {u, v}});
  34.  
  35. 		adj[u].push_back(v); ++m; 
  36.  
  37. 		if(!isDirected && u != v){
  38. 			adj[v].push_back(u);
  39. 		}
  40. 	} 
  41.  
  42. 	void deleteEdge(int u, int v){ 
  43.  
  44. 		if(u >= n || v >=n || u < 0 || v < 0){
  45. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  46. 			return;
  47. 		}
  48.  
  49. 		auto itr = find(adj[u].begin(), adj[u].end(), v);
  50.  
  51. 		if(itr == adj[u].end()){ 
  52. 			cout<<"The edge doesn't exists in the graph.\n";
  53. 			return; 
  54. 		} 
  55.  
  56. 		adj[u].erase(itr); --m;
  57.  
  58. 		if(!isDirected && u != v){
  59. 			itr = find(adj[v].begin(), adj[v].end(), u);
  60. 			adj[v].erase(itr);
  61. 		}
  62. 	} 
  63.  
  64. 	void displayGraph(){ 
  65.  
  66. 		if(!m){ 
  67. 			cout<<"The graph is empty!!";
  68. 			return;
  69. 		} 
  70.  
  71. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  72.  
  73. 		for(int i = 0; i < n; ++i){ 
  74. 			cout<<"The edges from vertex "<<i<<":";
  75.  
  76. 			for(auto val: adj[i])  
  77. 				cout<<"->"<<val;
  78.  
  79. 			cout<<"\n"; 
  80. 		}
  81. 		cout<<"====================================================\n";
  82. 	}
  83.  
  84. 	void kruskals(){
  85. 		vector<set<int>> sets;
  86. 		vector<int> finalEdges;
  87.  
  88. 		int minSpanningWeight = 0;
  89. 		int counter = 1;
  90.  
  91. 		sort(weights.begin(), weights.end(), 
  92. 		[](pair<int, pair<int, int>> &a, pair<int, pair<int, int>> &b){ return a.first < b.first; });
  93.  
  94. 		for(int i = 0; i < weights.size(); ++i){
  95. 			auto val = weights[i];
  96.  
  97. 			int uidx = -1, vidx = -1;
  98.  
  99. 			for(int i=0; (uidx == -1 || vidx == -1) && i < sets.size(); ++i){
  100. 				if(uidx == -1 && sets[i].find(val.second.first) != sets[i].end()){
  101. 					uidx = i;
  102. 				}
  103.  
  104. 				if(vidx == -1 && sets[i].find(val.second.second) != sets[i].end()){
  105. 					vidx = i;
  106. 				}
  107. 			}
  108.  
  109. 			if(uidx != vidx || (uidx==-1 && vidx==-1)){
  110.  
  111. 				finalEdges.push_back(i);
  112.  
  113. 				minSpanningWeight += val.first;
  114.  
  115. 				if(uidx==-1 && vidx==-1){
  116. 					set<int> st({val.second.first, val.second.second});
  117.  
  118. 					sets.push_back(st);
  119. 				}
  120. 				else if(uidx == -1){
  121. 					sets[vidx].insert(val.second.first);
  122. 				}
  123. 				else if(vidx == -1){
  124. 					sets[uidx].insert(val.second.second);
  125. 				}
  126. 				else{
  127. 					if(uidx < vidx){
  128. 						sets[uidx].insert(sets[vidx].begin(), sets[vidx].end());
  129. 						sets[vidx].clear();
  130. 					}
  131. 					else{
  132. 						sets[vidx].insert(sets[uidx].begin(), sets[uidx].end());
  133. 						sets[uidx].clear();
  134. 					}
  135. 				}
  136. 			}
  137. 		}
  138.  
  139. 		cout<<"The edges in the Kruskal's minimum spanning tree are,\n";
  140.  
  141. 		for(auto idx: finalEdges){
  142. 			cout<<weights[idx].second.first<<" -> "<<weights[idx].second.second
  143. 			<<" | Weight: "<<weights[idx].first<<"\n";
  144. 		}
  145.  
  146. 		cout<<"The minimum spanning tree weight: "<<minSpanningWeight<<"\n";
  147. 		cout<<"====================================================\n";
  148. 	}
  149.  
  150. 	void swap(vector<int> &arr, int i, int j){
  151. 		if(arr[i] != arr[j]){
  152. 			int temp = arr[i];
  153. 			arr[i] = arr[j];
  154. 			arr[j] = temp;
  155. 		}
  156. 	}
  157.  
  158. 	void heapify(vector<int> &nodes, vector<int> &positions, vector<int> &keys, int i, int tot){
  159. 		int smallest = i;
  160. 		int left = 2 * smallest + 1, right = left + 1;
  161.  
  162. 		if(left < tot && keys[nodes[left]] < keys[nodes[smallest]])
  163. 			smallest = left;
  164.  
  165. 		if(right < tot && keys[nodes[right]] < keys[nodes[smallest]])
  166. 			smallest = right;
  167.  
  168. 		if(smallest ^ i){
  169. 			swap(nodes, smallest, i);
  170.  
  171. 			swap(positions, nodes[smallest], nodes[i]);
  172.  
  173. 			heapify(nodes, positions, keys, smallest, tot);
  174. 		}
  175. 	}
  176.  
  177. 	void prims(int src){
  178. 		map<pair<int, int>, int> weightPairs;
  179.  
  180. 		for(auto val: weights){
  181. 			weightPairs[val.second] = val.first;
  182. 		}
  183.  
  184. 		/*================= Keys & predecessors initialization =================*/
  185. 		vector<int> keys(n, INT_MAX), predecessors(n, -1), nodes(n), positions(n);
  186.  
  187. 		vector<bool> visited(n, false);
  188. 		/*================= Keys & predecessors initialization =================*/
  189.  
  190. 		keys[src] = 0;
  191.  
  192. 		for(int i = 0; i < n; ++i){
  193. 			nodes[i] = i;
  194. 			positions[i] = i;
  195. 		}
  196.  
  197. 		for(int i=n/2-1; i > -1; --i){ // [O(n)]
  198. 			heapify(nodes, positions, keys, i, n);
  199. 		}
  200.  
  201. 		/*======================= Start extracting min from heap ========================*/
  202.  
  203. 		for(int i = n-1; i > 0; --i){ // [O(n)]
  204. 	        int u = nodes[0];
  205. 	        visited[u] = true;
  206.  
  207. 	        // cout<<"Popped: "<<u<<"\n";
  208.  
  209. 	        swap(nodes, 0, i);
  210. 	        swap(positions, nodes[0], nodes[i]);
  211.  
  212. 	        heapify(nodes, positions, keys, 0, i); // [O(log(n))]
  213.  
  214. 			for(auto v: adj[u]){ // [O(m)]
  215.  
  216. 				int weightOfUandV = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
  217.  
  218. 				if(!visited[v] && weightOfUandV < keys[v]){
  219. 					// cout<<"weight: "<<weightOfUandV<<" Node: "<<v<<"\n";
  220. 					predecessors[v] = u;
  221. 					keys[v] = weightOfUandV;
  222.  
  223. 					/*=============== Re-Position [O(log(n))] ================*/
  224. 					for(int vPos = positions[v]; 
  225. 						vPos && keys[ nodes[vPos] ] < keys[ nodes[(vPos - 1)/2] ]; 
  226. 						vPos = (vPos - 1)/2)
  227. 					{
  228. 						swap(nodes, vPos, (vPos - 1)/2);
  229. 						swap(positions, nodes[vPos], nodes[(vPos - 1)/2]);
  230. 					}
  231. 					/*=============== Re-Position [O(log(n))] ================*/
  232. 				}
  233. 			}
  234. 	    }
  235.  
  236. 		/*======================= End of extracting min from heap ========================*/
  237.  
  238. 		cout<<"The edges in the Prim's minimum spanning tree are,\n";
  239.  
  240. 		int minSpanningWeight = 0;
  241.  
  242. 		for(int u = 0; u < n; ++u){
  243. 			if(u != src){
  244. 				int v = predecessors[u];
  245. 				int wei = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
  246.  
  247. 				minSpanningWeight += wei;
  248.  
  249. 				cout<<u<<" -> "<<v<<" | Weight: "<<wei<<"\n";
  250. 			}
  251. 		}
  252.  
  253. 		cout<<"The minimum spanning tree weight: "<<minSpanningWeight<<"\n";
  254. 		cout<<"====================================================\n";
  255. 	} 
  256. };
  257.  
  258. int main() {
  259. 	// your code goes here
  260. 	int n, u, v, w; cin>>n;
  261.  
  262. 	Graph g(n, 0);
  263.  
  264. 	cin>>n;
  265.  
  266. 	for(int i=0; i < n; ++i){
  267. 		cin>>u>>v>>w;
  268. 		g.insertEdge(u,v,w);
  269. 	}
  270.  
  271. 	g.displayGraph();
  272.  
  273. 	g.kruskals();
  274.  
  275. 	cin>>u;
  276. 	cout<<"Enter the source vertex for prim's algorithm: "<<u<<"\n";
  277.  
  278. 	g.prims(u);
  279.  
  280. 	return 0;
  281. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
9
13
0 1 4
1 2 8
2 3 7
3 4 9
4 5 10
5 6 2
6 7 1
7 0 8
7 1 11
7 8 7
6 8 6
8 2 2
5 2 4
6
stdout
copy 
Total # edges in the graph: 13
The edges from vertex 0:->1->7
The edges from vertex 1:->0->2->7
The edges from vertex 2:->1->3->8->5
The edges from vertex 3:->2->4
The edges from vertex 4:->3->5
The edges from vertex 5:->4->6->2
The edges from vertex 6:->5->7->8
The edges from vertex 7:->6->0->1->8
The edges from vertex 8:->7->6->2
====================================================
The edges in the Kruskal's minimum spanning tree are,
6 -> 7 | Weight: 1
5 -> 6 | Weight: 2
8 -> 2 | Weight: 2
0 -> 1 | Weight: 4
5 -> 2 | Weight: 4
2 -> 3 | Weight: 7
1 -> 2 | Weight: 8
3 -> 4 | Weight: 9
The minimum spanning tree weight: 37
====================================================
Enter the source vertex for prim's algorithm: 6
The edges in the Prim's minimum spanning tree are,
0 -> 1 | Weight: 4
1 -> 2 | Weight: 8
2 -> 5 | Weight: 4
3 -> 2 | Weight: 7
4 -> 3 | Weight: 9
5 -> 6 | Weight: 2
7 -> 6 | Weight: 1
8 -> 2 | Weight: 2
The minimum spanning tree weight: 37
====================================================
https://ideone.com/UdCkpn
Minimal spanning tree using Kruskal's, Prim's || Time complexity: O(E log V)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!