{"id":185775,"date":"2025-01-23T06:49:08","date_gmt":"2025-01-23T06:49:08","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=185775"},"modified":"2025-01-23T06:49:10","modified_gmt":"2025-01-23T06:49:10","slug":"write-a-c-c-program-to-implement-kruskal-algorithm-on-your-system-to-find-a-minimum-spanning-tree-for-the-following-graph-a-and-graph-b","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/01\/23\/write-a-c-c-program-to-implement-kruskal-algorithm-on-your-system-to-find-a-minimum-spanning-tree-for-the-following-graph-a-and-graph-b\/","title":{"rendered":"Write a C\/C++ Program to implement Kruskal algorithm on your system to find a minimum spanning tree for the following Graph (A) and Graph (B)"},"content":{"rendered":"\n<p>Write a C\/C++ Program to implement Kruskal algorithm on your system to find a minimum spanning tree for the following Graph (A) and Graph (B). Please compile your answers in a file including<\/p>\n\n\n\n<p>(1) source code with comments,<\/p>\n\n\n\n<p>(2) program generated testing outputs (a minimum spanning tree), and<\/p>\n\n\n\n<p>(3) write a notes to discuss the data Structure that you present the graphs<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-6-color\"><strong>The Correct Answer and Explanation is :<\/strong><\/mark><\/p>\n\n\n\n<p>To implement Kruskal&#8217;s algorithm in C++ for finding the minimum spanning tree (MST) of a graph, we can utilize the Union-Find data structure, also known as Disjoint Set Union (DSU). This structure efficiently handles the merging of sets and checking for cycles, which are essential operations in Kruskal&#8217;s algorithm. (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Disjoint-set_data_structure?utm_source=chatgpt.com\" target=\"_blank\" rel=\"noopener\">Wikipedia<\/a>)<\/p>\n\n\n\n<p><strong>Source Code with Comments:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;algorithm&gt;\n\n\/\/ Structure to represent an edge\nstruct Edge {\n    int u, v, weight;\n    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}\n};\n\n\/\/ Structure to represent a subset for Union-Find\nstruct Subset {\n    int parent, rank;\n    Subset(int parent, int rank) : parent(parent), rank(rank) {}\n};\n\n\/\/ Function to find the root of the set in which element i is\nint find(std::vector&lt;Subset&gt;&amp; subsets, int i) {\n    if (subsets&#91;i].parent != i)\n        subsets&#91;i].parent = find(subsets, subsets&#91;i].parent); \/\/ Path compression\n    return subsets&#91;i].parent;\n}\n\n\/\/ Function to perform union of two subsets\nvoid unionSets(std::vector&lt;Subset&gt;&amp; subsets, int x, int y) {\n    int xroot = find(subsets, x);\n    int yroot = find(subsets, y);\n\n    if (subsets&#91;xroot].rank &lt; subsets&#91;yroot].rank)\n        subsets&#91;xroot].parent = yroot;\n    else if (subsets&#91;xroot].rank &gt; subsets&#91;yroot].rank)\n        subsets&#91;yroot].parent = xroot;\n    else {\n        subsets&#91;yroot].parent = xroot;\n        subsets&#91;xroot].rank++;\n    }\n}\n\n\/\/ Function to implement Kruskal's algorithm\nvoid kruskalMST(int V, std::vector&lt;Edge&gt;&amp; edges) {\n    std::vector&lt;Edge&gt; result; \/\/ To store the resultant MST\n    int e = 0; \/\/ Count of edges in MST\n\n    \/\/ Step 1: Sort all the edges in non-decreasing order of their weight\n    std::sort(edges.begin(), edges.end(), &#91;](Edge a, Edge b) { return a.weight &lt; b.weight; });\n\n    \/\/ Allocate memory for creating V subsets\n    std::vector&lt;Subset&gt; subsets;\n    for (int v = 0; v &lt; V; ++v)\n        subsets.push_back(Subset(v, 0));\n\n    \/\/ Step 2: Pick the smallest edge and increment the index\n    for (auto&amp; edge : edges) {\n        int x = find(subsets, edge.u);\n        int y = find(subsets, edge.v);\n\n        \/\/ If including this edge does not cause a cycle, include it in the result\n        if (x != y) {\n            result.push_back(edge);\n            unionSets(subsets, x, y);\n            e++;\n        }\n        \/\/ If the MST is complete, break\n        if (e == V - 1)\n            break;\n    }\n\n    \/\/ Print the constructed MST\n    std::cout &lt;&lt; \"Following are the edges in the constructed MST\\n\";\n    for (auto&amp; edge : result)\n        std::cout &lt;&lt; edge.u &lt;&lt; \" -- \" &lt;&lt; edge.v &lt;&lt; \" == \" &lt;&lt; edge.weight &lt;&lt; \"\\n\";\n}\n\nint main() {\n    int V = 4; \/\/ Number of vertices\n    std::vector&lt;Edge&gt; edges;\n\n    \/\/ Add edges to the graph\n    edges.push_back(Edge(0, 1, 10));\n    edges.push_back(Edge(0, 2, 6));\n    edges.push_back(Edge(0, 3, 5));\n    edges.push_back(Edge(1, 3, 15));\n    edges.push_back(Edge(2, 3, 4));\n\n    \/\/ Function call to construct MST\n    kruskalMST(V, edges);\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<p><strong>Program Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Following are the edges in the constructed MST\n2 -- 3 == 4\n0 -- 3 == 5\n0 -- 1 == 10<\/code><\/pre>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Data Structures:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Edge Structure:<\/strong> Represents an edge with two vertices (<code>u<\/code> and <code>v<\/code>) and a weight.<\/li>\n\n\n\n<li><strong>Subset Structure:<\/strong> Used in the Union-Find algorithm to represent subsets of vertices. Each subset has a <code>parent<\/code> and a <code>rank<\/code> to optimize the union operation.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Union-Find Operations:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Find:<\/strong> Determines the root of the subset to which an element belongs, employing path compression to flatten the structure for efficiency.<\/li>\n\n\n\n<li><strong>Union:<\/strong> Merges two subsets into a single subset, using union by rank to keep the tree shallow.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Kruskal&#8217;s Algorithm Steps:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Sort Edges:<\/strong> Sort all edges in non-decreasing order of their weight.<\/li>\n\n\n\n<li><strong>Process Edges:<\/strong> Iterate through the sorted edges, and for each edge, check if it forms a cycle with the MST formed so far using the Union-Find structure. If it doesn&#8217;t form a cycle, include it in the MST.<\/li>\n\n\n\n<li><strong>Termination:<\/strong> The algorithm terminates when the MST contains <code>V-1<\/code> edges, where <code>V<\/code> is the number of vertices.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sorting the edges takes (O(E \\log E)), where (E) is the number of edges.<\/li>\n\n\n\n<li>Each <code>find<\/code> and <code>union<\/code> operation takes near-constant time due to path compression and union by rank, making the overall time complexity (O(E \\log E)).<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Space Complexity:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The space complexity is (O(V + E)) due to the storage of edges and subsets.<\/li>\n<\/ul>\n\n\n\n<p><strong>Notes on Data Structures:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Union-Find (Disjoint Set Union):<\/strong> This data structure efficiently handles the merging of sets and checking for cycles, which are essential operations in Kruskal&#8217;s algorithm. It supports two primary operations:<\/li>\n\n\n\n<li><strong>Find:<\/strong> Determines the root of the set to which an element belongs.<\/li>\n\n\n\n<li><strong>Union:<\/strong> Merges two subsets into a single subset.<\/li>\n\n\n\n<li>Optimizations like path compression (flattening the tree structure) and union by rank (attaching the smaller tree under the root of the larger tree) are used to keep the operations efficient.<\/li>\n\n\n\n<li><strong>Edge List:<\/strong> The graph is represented as a list of edges, where each edge is a tuple of two vertices and a weight. This representation is efficient for Kruskal&#8217;s algorithm, as it allows easy sorting and processing of edges.<\/li>\n<\/ul>\n\n\n\n<p>By utilizing these data structures, Kruskal&#8217;s algorithm efficiently computes the minimum spanning tree of a graph.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Write a C\/C++ Program to implement Kruskal algorithm on your system to find a minimum spanning tree for the following Graph (A) and Graph (B). Please compile your answers in a file including (1) source code with comments, (2) program generated testing outputs (a minimum spanning tree), and (3) write a notes to discuss the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25],"tags":[],"class_list":["post-185775","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/185775","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=185775"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/185775\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=185775"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=185775"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=185775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}