{"id":39,"date":"2026-06-28T12:40:12","date_gmt":"2026-06-28T12:40:12","guid":{"rendered":"https:\/\/algovelgo.com\/?p=39"},"modified":"2026-06-28T13:01:04","modified_gmt":"2026-06-28T13:01:04","slug":"kruskal-algorithm-all-you-need-to-know","status":"publish","type":"post","link":"https:\/\/algovelgo.com\/?p=39","title":{"rendered":"Kruskal Algorithm : All you need to know"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Kruskal\u2019s Algorithm: A Greedy Approach to Minimum Spanning Trees<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Spanning trees are fundamental to network design, cluster analysis, and routing protocols. In this guide, we will break down <strong>Kruskal\u2019s Algorithm<\/strong>, one of the most elegant and widely-used greedy algorithms in computer science.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Before moving to understanding more of Kruskal Algorithm, you should be aware of below tersm<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>Term<\/td><td>Definition<\/td><\/tr><tr><td>Spanning Tree <\/td><td>A tree that connects all vertices using minimum<br>edges (V-1 for V vertices)<\/td><\/tr><tr><td>Minimum Spanning Tree (MST) <\/td><td>A spanning tree with minimum total edge<br>weight<\/td><\/tr><tr><td>Cycle<\/td><td>A path that starts and ends at the same vertex<\/td><\/tr><tr><td>Acyclic<\/td><td>A graph with no cycles<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">1. The Spanning Tree Problem<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let\u2019s define the problem we are trying to solve:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Given:<\/strong> A connected, weighted, and undirected graph (G = (V, E)), where (V) is the set of vertices (nodes) and (E) is the set of edges.<\/li>\n\n\n\n<li><strong>Goal:<\/strong> Find a subset of edges that connects all vertices in the graph together without any cycles, such that the total sum of the edge weights is minimized.<\/li>\n\n\n\n<li><strong>Output:<\/strong> A set of (V &#8211; 1) edges forming the <strong>Minimum Spanning Tree (MST)<\/strong>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">What exactly is a Spanning Tree?<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">A <strong>spanning tree<\/strong> of a graph is a subgraph that:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Spans:<\/strong> It connects all (V) vertices.<\/li>\n\n\n\n<li><strong>Is a Tree:<\/strong> It is acyclic (contains no cycles).<\/li>\n\n\n\n<li><strong>Has minimal edges:<\/strong> It contains exactly (V &#8211; 1) edges.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">A <strong>Minimum Spanning Tree (MST)<\/strong> is simply a spanning tree whose sum of edge weights is the smallest possible among all potential spanning trees.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">2. The Core Insight<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Kruskal&#8217;s algorithm works <strong>greedily<\/strong>. It sorts all edges in ascending order of their weights and adds them one by one, skipping any edge that would form a cycle.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This greedy strategy is mathematically justified by the <strong>Cut Property<\/strong>:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">[!IMPORTANT]<br><strong>The Cut Property:<\/strong><br>For any cut (partition) of the vertices in a graph, the minimum-weight edge crossing the cut must belong to some Minimum Spanning Tree of the graph.<\/p>\n<\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">By always selecting the cheapest available edge that connects two previously disconnected components, Kruskal&#8217;s algorithm builds up the optimal global solution through locally optimal choices.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">3. Intuition with an Analogy: The Cable Network Planner<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Imagine you are a network engineer tasked with connecting a series of remote cities with fiber-optic cables:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You have a map of all cities and a list of all potential connection paths along with their costs.<\/li>\n\n\n\n<li>Your objective is simple: <strong>Connect all cities so they can communicate with one another using the lowest possible budget.<\/strong><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Your Strategy:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Sort your list of potential connections from cheapest to most expensive.<\/li>\n\n\n\n<li>Buy the cheapest cable on your list.<\/li>\n\n\n\n<li>Move to the next cheapest. If it connects a city that is not already connected to your network (either directly or indirectly), buy it.<\/li>\n\n\n\n<li>If a cable would connect two cities that <strong>already have a path between them<\/strong> (e.g., City A is connected to B, and B to C, so buying a cable A-C is redundant), skip it! Doing so would waste your budget and create a redundant loop (cycle).<\/li>\n\n\n\n<li>Stop once all cities are connected.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">This is exactly how Kruskal\u2019s algorithm behaves.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">4. DSU: The Engine of Kruskal&#8217;s Algorithm<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">To quickly check if adding an edge will form a cycle, Kruskal\u2019s algorithm relies on a highly efficient data structure: the <strong>Disjoint Set Union (DSU)<\/strong> or <strong>Union-Find<\/strong>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The DSU manages a collection of disjoint (non-overlapping) sets. Each set represents a connected component in our graph. It supports three core operations:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>make_set(x)<\/code>: Initializes a new set containing only element (x).<\/li>\n\n\n\n<li><code>find(x)<\/code>: Returns the representative (or &#8220;root&#8221;) of the set containing (x). If two elements have the same representative, they belong to the same component.<\/li>\n\n\n\n<li><code>union(x, y)<\/code>: Merges the set containing (x) with the set containing (y).<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">5. Step-by-Step Algorithm<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Sort:<\/strong> Sort all edges in the graph in ascending order of their weights.<\/li>\n\n\n\n<li><strong>Initialize:<\/strong> Initialize the DSU such that each vertex (v \\in V) is in its own independent set.<\/li>\n\n\n\n<li><strong>Iterate:<\/strong> For each sorted edge (e = (u, v)) with weight (w):<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Call <code>find(u)<\/code> and <code>find(v)<\/code> to locate their components.<\/li>\n\n\n\n<li><strong>If the components are different<\/strong> (<code>find(u) != find(v)<\/code>):\n<ul class=\"wp-block-list\">\n<li>Add edge ((u, v)) to your MST.<\/li>\n\n\n\n<li>Call <code>union(u, v)<\/code> to merge the sets.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>If they are the same<\/strong> (<code>find(u) == find(v)<\/code>):\n<ul class=\"wp-block-list\">\n<li>Skip the edge to prevent a cycle.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Terminate:<\/strong> Stop when your MST has exactly (V &#8211; 1) edges.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">6. Pseudocode<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>def kruskal_mst(graph):\n    # Initialize MST\n    mst = &#91;]\n    mst_weight = 0\n\n    # 1. Retrieve and sort all edges by weight\n    edges = graph.get_all_edges() # Returns list of (weight, u, v)\n    edges.sort()\n\n    # 2. Initialize DSU\n    dsu = DisjointSet(graph.num_vertices)\n\n    # 3. Iterate through sorted edges\n    for weight, u, v in edges:\n        # Check if u and v are in different components\n        if dsu.find(u) != dsu.find(v):\n            mst.append((u, v, weight))\n            mst_weight += weight\n            dsu.union(u, v)\n\n            # Optimization: Stop early if MST has V-1 edges\n            if len(mst) == graph.num_vertices - 1:\n                break\n\n    return mst, mst_weight<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">7. Step-by-Step Execution Example<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let\u2019s trace the algorithm on a graph with <strong>5 vertices (A, B, C, D, E)<\/strong> and <strong>8 weighted edges<\/strong>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">The Initial Graph<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">The graph is composed of&nbsp;<strong>5 vertices<\/strong>&nbsp;and&nbsp;<strong>8 weighted edges<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Vertices (V):<\/strong>&nbsp;<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><semantics><mrow><mi>A<\/mi><mo separator=\"true\">,<\/mo><mi>B<\/mi><mo separator=\"true\">,<\/mo><mi>C<\/mi><mo separator=\"true\">,<\/mo><mi>D<\/mi><mo separator=\"true\">,<\/mo><mi>E<\/mi><\/mrow><\/semantics><\/math><\/li>\n\n\n\n<li><strong>Weighted Edges (E):<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>B-C<\/strong>: Weight 1<\/li>\n\n\n\n<li><strong>A-C<\/strong>: Weight 2<\/li>\n\n\n\n<li><strong>D-E<\/strong>: Weight 2<\/li>\n\n\n\n<li><strong>A-B<\/strong>: Weight 4<\/li>\n\n\n\n<li><strong>B-D<\/strong>: Weight 5<\/li>\n\n\n\n<li><strong>B-E<\/strong>: Weight 6<\/li>\n\n\n\n<li><strong>C-D<\/strong>: Weight 8<\/li>\n\n\n\n<li><strong>C-E<\/strong>: Weight 10<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Sorted Edges List<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th class=\"has-text-align-left\" data-align=\"left\">Priority<\/th><th class=\"has-text-align-left\" data-align=\"left\">Edge<\/th><th class=\"has-text-align-left\" data-align=\"left\">Weight<\/th><th class=\"has-text-align-left\" data-align=\"left\">Action<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\">1<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B-C<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">1<\/td><td class=\"has-text-align-left\" data-align=\"left\">Evaluated first<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">2<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>A-C<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">2<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">3<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>D-E<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">2<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">4<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>A-B<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">4<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">5<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B-D<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">5<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">6<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B-E<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">6<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">7<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>C-D<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">8<\/td><td class=\"has-text-align-left\" data-align=\"left\">&#8211;<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\">8<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>C-E<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">10<\/td><td class=\"has-text-align-left\" data-align=\"left\">Evaluated last<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Step-by-Step Trace<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Step 1: Initialize<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Current components:<\/strong> <code>{A}<\/code>, <code>{B}<\/code>, <code>{C}<\/code>, <code>{D}<\/code>, <code>{E}<\/code><\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>0<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Step 2: Process Edge (B-C, Weight 1)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>find(B) = B<\/code> and <code>find(C) = C<\/code>.<\/li>\n\n\n\n<li>Since (B) and (C) are in different components, we <strong>ADD<\/strong> this edge to the MST.<\/li>\n\n\n\n<li>Merge components: <code>union(B, C)<\/code>.<\/li>\n\n\n\n<li><strong>Current components:<\/strong> <code>{A}<\/code>, <code>{B, C}<\/code>, <code>{D}<\/code>, <code>{E}<\/code><\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[B-C]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>1<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Step 3: Process Edge (A-C, Weight 2)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>find(A) = A<\/code> and <code>find(C) = C<\/code> (represented by component <code>{B, C}<\/code>).<\/li>\n\n\n\n<li>Since (A) and (C) are in different components, we <strong>ADD<\/strong> this edge to the MST.<\/li>\n\n\n\n<li>Merge components: <code>union(A, C)<\/code>.<\/li>\n\n\n\n<li><strong>Current components:<\/strong> <code>{A, B, C}<\/code>, <code>{D}<\/code>, <code>{E}<\/code><\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[B-C, A-C]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>3<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Step 4: Process Edge (D-E, Weight 2)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>find(D) = D<\/code> and <code>find(E) = E<\/code>.<\/li>\n\n\n\n<li>Since (D) and (E) are in different components, we <strong>ADD<\/strong> this edge to the MST.<\/li>\n\n\n\n<li>Merge components: <code>union(D, E)<\/code>.<\/li>\n\n\n\n<li><strong>Current components:<\/strong> <code>{A, B, C}<\/code>, <code>{D, E}<\/code><\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[B-C, A-C, D-E]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>5<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Step 5: Process Edge (A-B, Weight 4)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>find(A) = C<\/code> (representative of <code>{A, B, C}<\/code>) and <code>find(B) = C<\/code> (representative of <code>{A, B, C}<\/code>).<\/li>\n\n\n\n<li>Since (A) and (B) belong to the <strong>same component<\/strong>, adding this edge would create a cycle ((A-B-C-A)).<\/li>\n\n\n\n<li>We <strong>SKIP<\/strong> this edge.<\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[B-C, A-C, D-E]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>5<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Step 6: Process Edge (B-D, Weight 5)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>find(B) = C<\/code> (representative of <code>{A, B, C}<\/code>) and <code>find(D) = E<\/code> (representative of <code>{D, E}<\/code>).<\/li>\n\n\n\n<li>Since (B) and (D) are in different components, we <strong>ADD<\/strong> this edge to the MST.<\/li>\n\n\n\n<li>Merge components: <code>union(B, D)<\/code>.<\/li>\n\n\n\n<li><strong>Current components:<\/strong> <code>{A, B, C, D, E}<\/code><\/li>\n\n\n\n<li><strong>MST edges:<\/strong> <code>[B-C, A-C, D-E, B-D]<\/code><\/li>\n\n\n\n<li><strong>MST total weight:<\/strong> <code>10<\/code><\/li>\n\n\n\n<li><strong>Status:<\/strong> MST is complete because it has selected (V-1 = 4) edges.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Final Result<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">All vertices are now fully connected with a minimal cost path:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">[A \\longleftrightarrow C \\longleftrightarrow B \\longleftrightarrow D \\longleftrightarrow E]<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Selected Edges:<\/strong> B-C (1), A-C (2), D-E (2), B-D (5)<\/li>\n\n\n\n<li><strong>Total weight:<\/strong> <strong>10<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">8. Complexity Analysis<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Time Complexity: (O(E \\log E)) or (O(E \\log V))<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Sorting Edges:<\/strong> Sorting (E) edges takes (O(E \\log E)) time.<\/li>\n\n\n\n<li><strong>DSU Operations:<\/strong> We perform at most (2E) <code>find<\/code> operations and (V-1) <code>union<\/code> operations. With path compression and union by rank, these take (O(E \\cdot \\alpha(V))) time.<\/li>\n\n\n\n<li><strong>Dominant term:<\/strong> Since (\\alpha(V)) is practically a constant, the sorting step dominates the runtime. Thus, the total complexity is:<br>[O(E \\log E)]<br>Since (E \\le V^2), we have (\\log E \\le \\log(V^2) = 2\\log V). This means the time complexity can also be written as:<br>[O(E \\log V)]<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Space Complexity: (O(V + E))<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>(O(E)) to store the list of edges.<\/li>\n\n\n\n<li>(O(V)) for the DSU parent and rank arrays.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">9. Kruskal\u2019s Algorithm: Pros and Cons<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Advantages &amp; Strengths<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Optimal for Sparse Graphs:<\/strong> Runs extremely fast when (E) is relatively small (e.g. (E \\approx V)).<\/li>\n\n\n\n<li><strong>Simple Intuition:<\/strong> Very straightforward to understand, explain, and write.<\/li>\n\n\n\n<li><strong>Negative Edge Weights:<\/strong> Works perfectly with negative weights (unlike Dijkstra\u2019s shortest path algorithm).<\/li>\n\n\n\n<li><strong>Minimum Spanning Forests:<\/strong> If the graph is disconnected, it naturally terminates by finding the MST for each isolated component (producing a Spanning Forest).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Limitations &amp; Constraints<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Undirected Graphs Only:<\/strong> Cannot be applied directly to directed graphs (finding an MST on directed graphs requires <em>Edmonds&#8217; Algorithm<\/em>).<\/li>\n\n\n\n<li><strong>Inefficient for Dense Graphs:<\/strong> When (E \\approx V^2), sorting all edges takes (O(V^2 \\log V)). Prim&#8217;s algorithm with a Fibonacci heap runs in (O(E + V \\log V)), which is faster.<\/li>\n\n\n\n<li><strong>Not for Shortest Paths:<\/strong> It is crucial to remember that an MST minimizes <strong>total network cost<\/strong>, not the distance between specific pairs of vertices. If you need the shortest path from a source to other vertices, use <strong>Dijkstra&#8217;s Algorithm<\/strong>.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">10. Kruskal\u2019s vs. Prim\u2019s Algorithm<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th class=\"has-text-align-left\" data-align=\"left\">Feature<\/th><th class=\"has-text-align-left\" data-align=\"left\">Kruskal&#8217;s Algorithm<\/th><th class=\"has-text-align-left\" data-align=\"left\">Prim&#8217;s Algorithm<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>Approach<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">Edge-centric (greedily adds sorted edges)<\/td><td class=\"has-text-align-left\" data-align=\"left\">Vertex-centric (grows a tree from a source)<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>Best Suited For<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>Sparse graphs<\/strong> ((E \\approx V))<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>Dense graphs<\/strong> ((E \\approx V^2))<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>Time Complexity<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">(O(E \\log E))<\/td><td class=\"has-text-align-left\" data-align=\"left\">(O(E \\log V)) (with Binary Heap)<br>(O(E + V \\log V)) (with Fibonacci Heap)<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>Cycle Detection<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">Handled by <strong>Disjoint Set Union (DSU)<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">Handled by tracking visited nodes<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>Data Structure<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\">Disjoint Set Union (DSU), Array<\/td><td class=\"has-text-align-left\" data-align=\"left\">Priority Queue \/ Heap<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<meta charset=\"UTF-8\">\n<meta name=\"viewport\" content=\"width=device-width, initial-scale=1.0\">\n<title>Kruskal&#8217;s Algorithm Step-by-Step Visualizer<\/title>\n\n<!-- Fonts -->\n<link rel=\"preconnect\" href=\"https:\/\/fonts.googleapis.com\">\n<link rel=\"preconnect\" href=\"https:\/\/fonts.gstatic.com\" crossorigin=\"\">\n<link href=\"https:\/\/fonts.googleapis.com\/css2?family=Outfit:wght@400;500;600;700;800&amp;family=Plus+Jakarta+Sans:wght@400;500;600;700&amp;family=JetBrains+Mono:wght@400;500;600&amp;display=swap\" rel=\"stylesheet\">\n\n<style>\n  #kruskal-widget {\n    \/* Dark Theme Settings *\/\n    --bg-widget: #090f1d;\n    --bg-card: rgba(17, 24, 39, 0.7);\n    --bg-card-hover: rgba(31, 41, 55, 0.8);\n    --border-color: rgba(255, 255, 255, 0.08);\n    --text-main: #f3f4f6;\n    --text-muted: #9ca3af;\n    --text-inverse: #090f1d;\n    \n    \/* Status Theme Colors *\/\n    --color-primary: #3b82f6; \n    --color-mst: #10b981; \n    --color-skipped: #ef4444; \n    --color-active: #f59e0b;\n    \n    \/* Disjoint Set Color Mapping *\/\n    --comp-A: #3b82f6; \/* Blue *\/\n    --comp-B: #a855f7; \/* Purple *\/\n    --comp-C: #10b981; \/* Emerald *\/\n    --comp-D: #f97316; \/* Orange *\/\n    --comp-E: #ec4899; \/* Pink *\/\n    \n    \/* Neon glow effects *\/\n    --glow-mst: 0 0 15px rgba(16, 185, 129, 0.5);\n    --glow-active: 0 0 15px rgba(245, 158, 11, 0.6);\n    --glow-skipped: 0 0 15px rgba(239, 68, 68, 0.4);\n    --shadow-widget: 0 12px 40px rgba(0, 0, 0, 0.6);\n\n    \/* Scoped body properties *\/\n    font-family: 'Plus Jakarta Sans', sans-serif;\n    color: var(--text-main);\n    width: 100%;\n    max-width: 1100px;\n    margin: 1.5rem auto;\n    padding: 1.5rem;\n    background: var(--bg-widget);\n    border-radius: 16px;\n    box-shadow: var(--shadow-widget);\n    border: 1px solid var(--border-color);\n    transition: background 0.3s, border-color 0.3s, box-shadow 0.3s;\n    text-align: left;\n  }\n\n  #kruskal-widget[data-theme=\"light\"] {\n    \/* Light Theme Settings *\/\n    --bg-widget: #f8fafc;\n    --bg-card: rgba(255, 255, 255, 0.85);\n    --bg-card-hover: rgba(241, 245, 249, 0.95);\n    --border-color: rgba(15, 23, 42, 0.08);\n    --text-main: #0f172a;\n    --text-muted: #64748b;\n    --text-inverse: #ffffff;\n    \n    --color-primary: #2563eb;\n    --color-mst: #059669;\n    --color-skipped: #dc2626;\n    --color-active: #d97706;\n    \n    \/* Neon glow effects for light mode (subtle) *\/\n    --glow-mst: 0 4px 10px rgba(5, 150, 105, 0.2);\n    --glow-active: 0 4px 10px rgba(217, 119, 6, 0.2);\n    --glow-skipped: 0 4px 10px rgba(220, 38, 38, 0.15);\n    --shadow-widget: 0 12px 40px rgba(15, 23, 42, 0.08);\n  }\n\n  #kruskal-widget * {\n    box-sizing: border-box;\n    margin: 0;\n    padding: 0;\n  }\n\n  \/* Header Bar *\/\n  #kruskal-widget .widget-header {\n    display: flex;\n    justify-content: space-between;\n    align-items: center;\n    margin-bottom: 1.25rem;\n    border-bottom: 1px solid var(--border-color);\n    padding-bottom: 1rem;\n    flex-wrap: wrap;\n    gap: 1rem;\n  }\n\n  #kruskal-widget .title-area h2 {\n    font-family: 'Outfit', sans-serif;\n    font-size: 1.5rem;\n    font-weight: 700;\n    background: linear-gradient(135deg, var(--color-primary), var(--color-mst));\n    -webkit-background-clip: text;\n    -webkit-text-fill-color: transparent;\n    display: inline-block;\n  }\n\n  #kruskal-widget .title-area p {\n    font-size: 0.85rem;\n    color: var(--text-muted);\n    margin-top: 0.15rem;\n  }\n\n  \/* Header Buttons *\/\n  #kruskal-widget .header-controls {\n    display: flex;\n    align-items: center;\n    gap: 0.75rem;\n  }\n\n  #kruskal-widget .btn-icon {\n    background: rgba(255, 255, 255, 0.05);\n    border: 1px solid var(--border-color);\n    color: var(--text-main);\n    padding: 0.5rem 0.85rem;\n    border-radius: 8px;\n    cursor: pointer;\n    font-weight: 600;\n    font-size: 0.82rem;\n    display: flex;\n    align-items: center;\n    gap: 0.4rem;\n    transition: all 0.2s;\n  }\n\n  #kruskal-widget .btn-icon:hover {\n    background: rgba(255, 255, 255, 0.1);\n    border-color: var(--text-muted);\n  }\n\n  \/* Control Panel Card *\/\n  #kruskal-widget .controls-panel {\n    background: var(--bg-card);\n    backdrop-filter: blur(8px);\n    -webkit-backdrop-filter: blur(8px);\n    border: 1px solid var(--border-color);\n    border-radius: 12px;\n    padding: 0.85rem 1.25rem;\n    margin-bottom: 1.25rem;\n    display: flex;\n    flex-wrap: wrap;\n    align-items: center;\n    justify-content: space-between;\n    gap: 1rem;\n  }\n\n  #kruskal-widget .btn-group {\n    display: flex;\n    gap: 0.5rem;\n    flex-wrap: wrap;\n  }\n\n  #kruskal-widget .btn {\n    background: rgba(255, 255, 255, 0.06);\n    border: 1px solid var(--border-color);\n    color: var(--text-main);\n    padding: 0.5rem 1rem;\n    border-radius: 6px;\n    cursor: pointer;\n    font-weight: 600;\n    font-size: 0.85rem;\n    display: flex;\n    align-items: center;\n    gap: 0.4rem;\n    transition: background 0.2s, transform 0.1s, border-color 0.2s;\n  }\n\n  #kruskal-widget .btn:hover:not(:disabled) {\n    background: rgba(255, 255, 255, 0.12);\n    border-color: rgba(255, 255, 255, 0.2);\n  }\n\n  #kruskal-widget .btn:active:not(:disabled) {\n    transform: scale(0.97);\n  }\n\n  #kruskal-widget .btn:disabled {\n    opacity: 0.35;\n    cursor: not-allowed;\n  }\n\n  #kruskal-widget .btn.primary {\n    background: var(--color-primary);\n    border-color: transparent;\n    color: #ffffff;\n  }\n\n  #kruskal-widget .btn.primary:hover:not(:disabled) {\n    background: #2563eb;\n  }\n\n  #kruskal-widget .slider-container {\n    display: flex;\n    align-items: center;\n    gap: 0.75rem;\n    flex-grow: 1;\n    max-width: 380px;\n  }\n\n  #kruskal-widget .slider-label {\n    font-size: 0.82rem;\n    color: var(--text-muted);\n    white-space: nowrap;\n    min-width: 80px;\n    font-weight: 600;\n    font-family: 'Outfit', sans-serif;\n  }\n\n  #kruskal-widget input[type=\"range\"] {\n    -webkit-appearance: none;\n    width: 100%;\n    height: 5px;\n    border-radius: 3px;\n    background: var(--border-color);\n    outline: none;\n    cursor: pointer;\n  }\n\n  #kruskal-widget input[type=\"range\"]::-webkit-slider-thumb {\n    -webkit-appearance: none;\n    width: 15px;\n    height: 15px;\n    border-radius: 50%;\n    background: var(--color-primary);\n    transition: transform 0.1s;\n  }\n\n  #kruskal-widget input[type=\"range\"]::-webkit-slider-thumb:hover {\n    transform: scale(1.2);\n  }\n\n  \/* Speed Selector *\/\n  #kruskal-widget .speed-container {\n    display: flex;\n    align-items: center;\n    gap: 0.5rem;\n  }\n\n  #kruskal-widget .speed-label {\n    font-size: 0.8rem;\n    color: var(--text-muted);\n    font-weight: 600;\n  }\n\n  #kruskal-widget .speed-select {\n    background: rgba(255, 255, 255, 0.05);\n    border: 1px solid var(--border-color);\n    color: var(--text-main);\n    padding: 0.35rem 0.6rem;\n    border-radius: 6px;\n    outline: none;\n    font-size: 0.8rem;\n    font-weight: 600;\n    cursor: pointer;\n  }\n\n  \/* Visualizer Layout Grid *\/\n  #kruskal-widget .visualizer-grid {\n    display: grid;\n    grid-template-columns: 1.2fr 0.8fr;\n    gap: 1.25rem;\n    margin-bottom: 1.25rem;\n  }\n\n  @media (max-width: 900px) {\n    #kruskal-widget .visualizer-grid {\n      grid-template-columns: 1fr;\n    }\n  }\n\n  \/* Card Panels *\/\n  #kruskal-widget .panel-card {\n    background: var(--bg-card);\n    backdrop-filter: blur(12px);\n    -webkit-backdrop-filter: blur(12px);\n    border: 1px solid var(--border-color);\n    border-radius: 12px;\n    padding: 1.25rem;\n    box-shadow: 0 4px 20px rgba(0,0,0,0.15);\n    display: flex;\n    flex-direction: column;\n    position: relative;\n    overflow: hidden;\n    transition: background 0.3s, border-color 0.3s;\n  }\n\n  #kruskal-widget .panel-title {\n    font-family: 'Outfit', sans-serif;\n    font-size: 1.1rem;\n    font-weight: 600;\n    margin-bottom: 1rem;\n    display: flex;\n    align-items: center;\n    gap: 0.5rem;\n    color: var(--text-main);\n    border-bottom: 1px solid var(--border-color);\n    padding-bottom: 0.5rem;\n  }\n\n  \/* Graph Canvas Box *\/\n  #kruskal-widget .graph-container {\n    display: flex;\n    justify-content: center;\n    align-items: center;\n    background: rgba(0, 0, 0, 0.2);\n    border-radius: 8px;\n    border: 1px solid rgba(255, 255, 255, 0.02);\n    padding: 0.5rem;\n    position: relative;\n    width: 100%;\n    height: auto;\n    aspect-ratio: 12 \/ 7;\n    margin-bottom: 1rem;\n  }\n\n  #kruskal-widget #graph-svg {\n    width: 100%;\n    height: 100%;\n  }\n\n  \/* SVG Edges *\/\n  #kruskal-widget .edge {\n    stroke: var(--text-muted);\n    stroke-opacity: 0.25;\n    stroke-width: 3;\n    stroke-linecap: round;\n    fill: none;\n    transition: all 0.3s ease;\n  }\n\n  #kruskal-widget .edge.unprocessed {\n    stroke-opacity: 0.25;\n    stroke-width: 3;\n  }\n\n  #kruskal-widget .edge.active {\n    stroke: var(--color-active);\n    stroke-width: 5;\n    stroke-opacity: 1;\n    filter: drop-shadow(var(--glow-active));\n    stroke-dasharray: 8 4;\n    animation: dash 1s linear infinite;\n  }\n\n  #kruskal-widget .edge.mst {\n    stroke: var(--color-mst);\n    stroke-width: 6;\n    stroke-opacity: 1;\n    filter: drop-shadow(var(--glow-mst));\n  }\n\n  #kruskal-widget .edge.skipped {\n    stroke: var(--color-skipped);\n    stroke-width: 3;\n    stroke-opacity: 0.4;\n    stroke-dasharray: 4 4;\n    filter: drop-shadow(var(--glow-skipped));\n  }\n\n  @keyframes dash {\n    to {\n      stroke-dashoffset: -12;\n    }\n  }\n\n  \/* Labels *\/\n  #kruskal-widget .edge-label-bg {\n    fill: var(--bg-widget);\n    rx: 4;\n    ry: 4;\n    stroke: var(--border-color);\n    stroke-width: 1;\n    transition: fill 0.3s, stroke 0.3s;\n  }\n\n  #kruskal-widget .edge-label {\n    fill: var(--text-main);\n    font-size: 11px;\n    font-weight: 700;\n    font-family: 'Outfit', sans-serif;\n    text-anchor: middle;\n    dominant-baseline: central;\n  }\n\n  #kruskal-widget .edge-label.active {\n    fill: var(--color-active);\n  }\n\n  #kruskal-widget .edge-label.mst {\n    fill: var(--color-mst);\n  }\n\n  #kruskal-widget .edge-label.skipped {\n    fill: var(--color-skipped);\n    text-decoration: line-through;\n  }\n\n  \/* Nodes styling *\/\n  #kruskal-widget .node-circle {\n    fill: var(--node-bg);\n    stroke: var(--node-stroke);\n    stroke-width: 3;\n    transition: all 0.3s ease;\n    cursor: pointer;\n  }\n\n  #kruskal-widget .node-text {\n    fill: var(--text-main);\n    font-size: 14px;\n    font-weight: 700;\n    font-family: 'Outfit', sans-serif;\n    text-anchor: middle;\n    dominant-baseline: central;\n    pointer-events: none;\n  }\n\n  \/* State & Details *\/\n  #kruskal-widget .step-desc {\n    font-size: 0.88rem;\n    line-height: 1.5;\n    color: var(--text-main);\n    background: rgba(0, 0, 0, 0.15);\n    border-left: 3.5px solid var(--color-primary);\n    padding: 0.75rem 1rem;\n    border-radius: 0 8px 8px 0;\n    margin-bottom: 1rem;\n    min-height: 60px;\n    transition: all 0.3s;\n  }\n\n  #kruskal-widget .step-desc.mst-update {\n    border-left-color: var(--color-mst);\n  }\n\n  #kruskal-widget .step-desc.skip-update {\n    border-left-color: var(--color-skipped);\n  }\n\n  #kruskal-widget .text-mst {\n    color: var(--color-mst);\n    font-weight: 600;\n  }\n\n  #kruskal-widget .text-skipped {\n    color: var(--color-skipped);\n    font-weight: 600;\n  }\n\n  \/* Disjoint Sets Display *\/\n  #kruskal-widget .state-section {\n    margin-bottom: 1rem;\n  }\n\n  #kruskal-widget .state-section:last-child {\n    margin-bottom: 0;\n  }\n\n  #kruskal-widget .state-section-title {\n    font-size: 0.72rem;\n    text-transform: uppercase;\n    letter-spacing: 0.08em;\n    color: var(--text-muted);\n    margin-bottom: 0.4rem;\n    font-weight: 700;\n  }\n\n  #kruskal-widget .badge-list {\n    display: flex;\n    flex-wrap: wrap;\n    gap: 0.5rem;\n  }\n\n  #kruskal-widget .comp-badge {\n    display: inline-flex;\n    align-items: center;\n    padding: 0.25rem 0.65rem;\n    border-radius: 6px;\n    font-size: 0.82rem;\n    font-weight: 700;\n    border: 1.5px solid currentColor;\n    font-family: 'JetBrains Mono', monospace;\n  }\n\n  \/* Tables *\/\n  #kruskal-widget .table-container {\n    background: rgba(0, 0, 0, 0.15);\n    border-radius: 8px;\n    border: 1px solid var(--border-color);\n    overflow: hidden;\n    margin-top: 0.4rem;\n  }\n\n  #kruskal-widget table {\n    width: 100%;\n    border-collapse: collapse;\n    font-size: 0.82rem;\n    text-align: left;\n  }\n\n  #kruskal-widget th, #kruskal-widget td {\n    padding: 0.45rem 0.6rem;\n    border-bottom: 1px solid var(--border-color);\n  }\n\n  #kruskal-widget th {\n    background: var(--table-header);\n    color: var(--text-muted);\n    font-weight: 600;\n    font-size: 0.72rem;\n    text-transform: uppercase;\n    letter-spacing: 0.05em;\n  }\n\n  #kruskal-widget tr:last-child td {\n    border-bottom: none;\n  }\n\n  #kruskal-widget .mono-cell {\n    font-family: 'JetBrains Mono', monospace;\n    font-weight: 600;\n  }\n\n  #kruskal-widget .updated-cell {\n    animation: highlight-cell 1.5s ease-out;\n  }\n\n  \/* Edge Checklist Side Panel *\/\n  #kruskal-widget .edge-table {\n    width: 100%;\n  }\n\n  #kruskal-widget .edge-row {\n    display: flex;\n    align-items: center;\n    justify-content: space-between;\n    padding: 0.45rem 0.6rem;\n    border-radius: 6px;\n    margin-bottom: 0.3rem;\n    border: 1px solid transparent;\n    transition: all 0.25s;\n    font-size: 0.85rem;\n  }\n\n  #kruskal-widget .edge-row.unprocessed {\n    opacity: 0.65;\n  }\n\n  #kruskal-widget .edge-row.comparing {\n    background: rgba(245, 158, 11, 0.08);\n    border-color: rgba(245, 158, 11, 0.3);\n    font-weight: 600;\n    position: relative;\n  }\n\n  #kruskal-widget .edge-row.comparing::before {\n    content: '\u2794';\n    position: absolute;\n    left: -12px;\n    color: var(--color-active);\n    animation: bounce-arrow 0.8s infinite alternate;\n  }\n\n  @keyframes bounce-arrow {\n    from { transform: translateX(0); }\n    to { transform: translateX(4px); }\n  }\n\n  #kruskal-widget .edge-row.added {\n    background: rgba(16, 185, 129, 0.08);\n    border-color: rgba(16, 185, 129, 0.2);\n    font-weight: 600;\n  }\n\n  #kruskal-widget .edge-row.skipped {\n    background: rgba(239, 68, 68, 0.04);\n    border-color: rgba(239, 68, 68, 0.15);\n    text-decoration: line-through;\n    opacity: 0.6;\n  }\n\n  #kruskal-widget .status-badge {\n    font-size: 0.68rem;\n    font-weight: 700;\n    padding: 0.15rem 0.4rem;\n    border-radius: 4px;\n    text-transform: uppercase;\n    letter-spacing: 0.02em;\n  }\n\n  #kruskal-widget .status-badge.unprocessed {\n    background: rgba(255, 255, 255, 0.05);\n    color: var(--text-muted);\n  }\n\n  #kruskal-widget .status-badge.comparing {\n    background: rgba(245, 158, 11, 0.15);\n    color: var(--color-active);\n    border: 1px solid rgba(245, 158, 11, 0.2);\n  }\n\n  #kruskal-widget .status-badge.added {\n    background: rgba(16, 185, 129, 0.15);\n    color: var(--color-mst);\n    border: 1px solid rgba(16, 185, 129, 0.2);\n  }\n\n  #kruskal-widget .status-badge.skipped {\n    background: rgba(239, 68, 68, 0.15);\n    color: var(--color-skipped);\n    border: 1px solid rgba(239, 68, 68, 0.2);\n  }\n\n  \/* Summary Bar *\/\n  #kruskal-widget .summary-bar {\n    display: grid;\n    grid-template-columns: 1fr 1.2fr;\n    gap: 1rem;\n    margin-top: auto;\n    padding-top: 1rem;\n    border-top: 1px solid var(--border-color);\n  }\n\n  #kruskal-widget .summary-item {\n    display: flex;\n    flex-direction: column;\n    gap: 0.2rem;\n  }\n\n  #kruskal-widget .summary-lbl {\n    font-size: 0.72rem;\n    text-transform: uppercase;\n    color: var(--text-muted);\n    font-weight: 700;\n    letter-spacing: 0.05em;\n  }\n\n  #kruskal-widget .summary-val {\n    font-family: 'Outfit', sans-serif;\n    font-size: 1.25rem;\n    font-weight: 800;\n  }\n\n  #kruskal-widget .summary-val.mst-val {\n    color: var(--color-mst);\n  }\n\n  #kruskal-widget .summary-box-list {\n    font-family: 'JetBrains Mono', monospace;\n    font-size: 0.75rem;\n    color: var(--text-main);\n    background: rgba(0, 0, 0, 0.15);\n    padding: 0.35rem 0.5rem;\n    border-radius: 6px;\n    min-height: 26px;\n    display: flex;\n    align-items: center;\n    flex-wrap: wrap;\n    gap: 0.3rem;\n  }\n\n  #kruskal-widget .summary-edge-tag {\n    background: rgba(255, 255, 255, 0.05);\n    border: 1px solid var(--border-color);\n    padding: 0.1rem 0.3rem;\n    border-radius: 4px;\n  }\n\n  \/* Details Info Grid *\/\n  #kruskal-widget .info-footer-grid {\n    display: grid;\n    grid-template-columns: 1fr 1fr;\n    gap: 1.25rem;\n    margin-top: 1.25rem;\n    border-top: 1px solid var(--border-color);\n    padding-top: 1.25rem;\n  }\n\n  @media (max-width: 768px) {\n    #kruskal-widget .info-footer-grid {\n      grid-template-columns: 1fr;\n    }\n  }\n\n  #kruskal-widget .info-list {\n    list-style: none;\n    display: flex;\n    flex-direction: column;\n    gap: 0.5rem;\n  }\n\n  #kruskal-widget .info-list li {\n    display: flex;\n    align-items: flex-start;\n    gap: 0.5rem;\n    font-size: 0.85rem;\n    line-height: 1.4;\n  }\n\n  #kruskal-widget .info-list li strong {\n    color: var(--text-main);\n  }\n\n  #kruskal-widget .info-list li .bullet-ok {\n    color: var(--color-mst);\n    flex-shrink: 0;\n    font-weight: bold;\n  }\n\n  #kruskal-widget .info-list li .bullet-no {\n    color: var(--color-skipped);\n    flex-shrink: 0;\n    font-weight: bold;\n  }\n\n  #kruskal-widget .footer-card {\n    background: rgba(255, 255, 255, 0.01);\n    border: 1px solid var(--border-color);\n    border-radius: 10px;\n    padding: 1rem;\n  }\n\n  #kruskal-widget .footer-card-title {\n    font-family: 'Outfit', sans-serif;\n    font-weight: 700;\n    font-size: 0.95rem;\n    margin-bottom: 0.6rem;\n    display: flex;\n    align-items: center;\n    gap: 0.4rem;\n  }\n\n  \/* Formula styling *\/\n  #kruskal-widget .formula {\n    font-family: 'JetBrains Mono', monospace;\n    background: rgba(0,0,0,0.2);\n    padding: 0.1rem 0.3rem;\n    border-radius: 4px;\n    font-size: 0.8rem;\n  }\n<\/style>\n\n<div class=\"widget-container\" id=\"kruskal-widget\" data-theme=\"dark\">\n  \n  <!-- Header Bar -->\n  <div class=\"widget-header\">\n    <div class=\"title-area\">\n      <h2>Kruskal&#8217;s Algorithm Visualizer<\/h2>\n      <p>Step-by-step Union-Find cycle detection on a weighted graph<\/p>\n    <\/div>\n    <div class=\"header-controls\">\n      <button id=\"btn-theme\" class=\"btn-icon\" onclick=\"toggleTheme()\" aria-label=\"Toggle Theme\">\n        <svg id=\"theme-icon-sun\" width=\"14\" height=\"14\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\" style=\"display:none;\">\n          <circle cx=\"12\" cy=\"12\" r=\"5\"><\/circle>\n          <line x1=\"12\" y1=\"1\" x2=\"12\" y2=\"3\"><\/line>\n          <line x1=\"12\" y1=\"21\" x2=\"12\" y2=\"23\"><\/line>\n          <line x1=\"4.22\" y1=\"4.22\" x2=\"5.64\" y2=\"5.64\"><\/line>\n          <line x1=\"18.36\" y1=\"18.36\" x2=\"19.78\" y2=\"19.78\"><\/line>\n          <line x1=\"1\" y1=\"12\" x2=\"3\" y2=\"12\"><\/line>\n          <line x1=\"21\" y1=\"12\" x2=\"23\" y2=\"12\"><\/line>\n          <line x1=\"4.22\" y1=\"19.78\" x2=\"5.64\" y2=\"18.36\"><\/line>\n          <line x1=\"18.36\" y1=\"5.64\" x2=\"19.78\" y2=\"4.22\"><\/line>\n        <\/svg>\n        <svg id=\"theme-icon-moon\" width=\"14\" height=\"14\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\">\n          <path d=\"M21 12.79A9 9 0 1 1 11.21 3 7 7 0 0 0 21 12.79z\"><\/path>\n        <\/svg>\n        <span id=\"theme-text\">Light Mode<\/span>\n      <\/button>\n    <\/div>\n  <\/div>\n\n  <!-- Main Controls Panel -->\n  <div class=\"controls-panel\">\n    <div class=\"btn-group\">\n      <button id=\"btn-prev\" class=\"btn\" onclick=\"prevStep()\" aria-label=\"Previous Step\">\n        <svg width=\"14\" height=\"14\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\"><path d=\"M15 18l-6-6 6-6\"><\/path><\/svg>\n        Prev\n      <\/button>\n      <button id=\"btn-play\" class=\"btn primary\" onclick=\"togglePlay()\" aria-label=\"Play or Pause\">\n        <svg id=\"play-icon\" width=\"12\" height=\"12\" viewBox=\"0 0 24 24\" fill=\"currentColor\"><polygon points=\"5,3 19,12 5,21\"><\/polygon><\/svg>\n        <span id=\"play-text\">Play<\/span>\n      <\/button>\n      <button id=\"btn-next\" class=\"btn\" onclick=\"nextStep()\" aria-label=\"Next Step\">\n        Next\n        <svg width=\"14\" height=\"14\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\"><path d=\"M9 18l6-6-6-6\"><\/path><\/svg>\n      <\/button>\n      <button id=\"btn-reset\" class=\"btn\" onclick=\"resetVisualizer()\" aria-label=\"Reset Visualizer\">\n        Reset\n      <\/button>\n    <\/div>\n\n    <div class=\"slider-container\">\n      <span class=\"slider-label\" id=\"step-label\">Step 1 \/ 7<\/span>\n      <input type=\"range\" id=\"step-slider\" min=\"0\" max=\"6\" value=\"0\" oninput=\"goToStep(parseInt(this.value))\">\n    <\/div>\n\n    <div class=\"speed-container\">\n      <span class=\"speed-label\">Speed:<\/span>\n      <select id=\"speed-select\" class=\"speed-select\" onchange=\"changeSpeed(this.value)\">\n        <option value=\"3500\">Slow<\/option>\n        <option value=\"2000\" selected=\"\">Normal<\/option>\n        <option value=\"1000\">Fast<\/option>\n      <\/select>\n    <\/div>\n  <\/div>\n\n  <!-- Visualizer Grid Layout -->\n  <div class=\"visualizer-grid\">\n    \n    <!-- Left Column: Graph Drawing & Disjoint-Set State -->\n    <div style=\"display: flex; flex-direction: column; gap: 1.25rem;\">\n      <div class=\"panel-card\">\n        <div class=\"panel-title\">\n          <svg width=\"16\" height=\"16\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\"><circle cx=\"18\" cy=\"5\" r=\"3\"><\/circle><circle cx=\"6\" cy=\"12\" r=\"3\"><\/circle><circle cx=\"18\" cy=\"19\" r=\"3\"><\/circle><path d=\"M9 12h6M9 12l6-5M9 12l6 7\"><\/path><\/svg>\n          Graph Canvas\n        <\/div>\n        \n        <div class=\"graph-container\">\n          <svg viewBox=\"0 0 600 350\" id=\"graph-svg\">\n            \n            <!-- Edges (Rendered behind) -->\n            <g id=\"edges-group\">\n              <line id=\"edge-A-B\" class=\"edge\" x1=\"120\" y1=\"90\" x2=\"300\" y2=\"90\"><\/line>\n              <line id=\"edge-B-D\" class=\"edge\" x1=\"300\" y1=\"90\" x2=\"480\" y2=\"90\"><\/line>\n              <line id=\"edge-A-C\" class=\"edge\" x1=\"120\" y1=\"90\" x2=\"120\" y2=\"260\"><\/line>\n              <line id=\"edge-B-C\" class=\"edge\" x1=\"300\" y1=\"90\" x2=\"120\" y2=\"260\"><\/line>\n              <line id=\"edge-B-E\" class=\"edge\" x1=\"300\" y1=\"90\" x2=\"300\" y2=\"260\"><\/line>\n              <line id=\"edge-D-E\" class=\"edge\" x1=\"480\" y1=\"90\" x2=\"300\" y2=\"260\"><\/line>\n              <line id=\"edge-C-E\" class=\"edge\" x1=\"120\" y1=\"260\" x2=\"300\" y2=\"260\"><\/line>\n              <!-- Curved Edge for C-D to avoid B-E intersection -->\n              <path id=\"edge-C-D\" class=\"edge\" d=\"M 120,260 Q 300,-80 480,90\"><\/path>\n            <\/g>\n\n            <!-- Edge Weight Labels -->\n            <g id=\"labels-group\">\n              <!-- A-B: weight 4 -->\n              <g transform=\"translate(210, 80)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-A-B\" class=\"edge-label\">4<\/text>\n              <\/g>\n              <!-- B-D: weight 5 -->\n              <g transform=\"translate(390, 80)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-B-D\" class=\"edge-label\">5<\/text>\n              <\/g>\n              <!-- A-C: weight 2 -->\n              <g transform=\"translate(105, 175)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-A-C\" class=\"edge-label\">2<\/text>\n              <\/g>\n              <!-- B-C: weight 1 -->\n              <g transform=\"translate(195, 160)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-B-C\" class=\"edge-label\">1<\/text>\n              <\/g>\n              <!-- B-E: weight 6 -->\n              <g transform=\"translate(315, 175)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-B-E\" class=\"edge-label\">6<\/text>\n              <\/g>\n              <!-- D-E: weight 2 -->\n              <g transform=\"translate(405, 160)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-D-E\" class=\"edge-label\">2<\/text>\n              <\/g>\n              <!-- C-E: weight 10 -->\n              <g transform=\"translate(210, 272)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-C-E\" class=\"edge-label\">10<\/text>\n              <\/g>\n              <!-- C-D: weight 8 (placed at apex of arch) -->\n              <g transform=\"translate(300, 36)\">\n                <rect class=\"edge-label-bg\" x=\"-11\" y=\"-11\" width=\"22\" height=\"22\"><\/rect>\n                <text id=\"weight-C-D\" class=\"edge-label\">8<\/text>\n              <\/g>\n            <\/g>\n\n            <!-- Nodes (Rendered on top) -->\n            <g id=\"nodes-group\">\n              <g id=\"node-A\">\n                <circle class=\"node-circle\" cx=\"120\" cy=\"90\" r=\"23\"><\/circle>\n                <text class=\"node-text\" x=\"120\" y=\"90\">A<\/text>\n              <\/g>\n              <g id=\"node-B\">\n                <circle class=\"node-circle\" cx=\"300\" cy=\"90\" r=\"23\"><\/circle>\n                <text class=\"node-text\" x=\"300\" y=\"90\">B<\/text>\n              <\/g>\n              <g id=\"node-D\">\n                <circle class=\"node-circle\" cx=\"480\" cy=\"90\" r=\"23\"><\/circle>\n                <text class=\"node-text\" x=\"480\" y=\"90\">D<\/text>\n              <\/g>\n              <g id=\"node-C\">\n                <circle class=\"node-circle\" cx=\"120\" cy=\"260\" r=\"23\"><\/circle>\n                <text class=\"node-text\" x=\"120\" y=\"260\">C<\/text>\n              <\/g>\n              <g id=\"node-E\">\n                <circle class=\"node-circle\" cx=\"300\" cy=\"260\" r=\"23\"><\/circle>\n                <text class=\"node-text\" x=\"300\" y=\"260\">E<\/text>\n              <\/g>\n            <\/g>\n          <\/svg>\n        <\/div>\n        \n        <!-- Union-Find Parent Pointers Table -->\n        <div class=\"state-section\">\n          <div class=\"state-section-title\">Disjoint Set (Union-Find) State<\/div>\n          <div class=\"table-container\">\n            <table>\n              <thead>\n                <tr>\n                  <th>Element<\/th>\n                  <th>A<\/th>\n                  <th>B<\/th>\n                  <th>C<\/th>\n                  <th>D<\/th>\n                  <th>E<\/th>\n                <\/tr>\n              <\/thead>\n              <tbody>\n                <tr id=\"parent-row\">\n                  <td style=\"font-weight:700; color:var(--text-muted);\">Parent<\/td>\n                  <td id=\"parent-A\" class=\"mono-cell\">A<\/td>\n                  <td id=\"parent-B\" class=\"mono-cell\">B<\/td>\n                  <td id=\"parent-C\" class=\"mono-cell\">C<\/td>\n                  <td id=\"parent-D\" class=\"mono-cell\">D<\/td>\n                  <td id=\"parent-E\" class=\"mono-cell\">E<\/td>\n                <\/tr>\n                <tr id=\"root-row\">\n                  <td style=\"font-weight:700; color:var(--text-muted);\">find(x)<\/td>\n                  <td id=\"root-A\" class=\"mono-cell\">A<\/td>\n                  <td id=\"root-B\" class=\"mono-cell\">B<\/td>\n                  <td id=\"root-C\" class=\"mono-cell\">C<\/td>\n                  <td id=\"root-D\" class=\"mono-cell\">D<\/td>\n                  <td id=\"root-E\" class=\"mono-cell\">E<\/td>\n                <\/tr>\n              <\/tbody>\n            <\/table>\n          <\/div>\n        <\/div>\n      <\/div>\n    <\/div>\n\n    <!-- Right Column: Current Step & Sorted Edges Checklist -->\n    <div style=\"display: flex; flex-direction: column; gap: 1.25rem;\">\n      \n      <!-- Current Step Description -->\n      <div class=\"panel-card\" style=\"flex-grow: 1;\">\n        <div class=\"panel-title\">\n          <svg width=\"16\" height=\"16\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\"><path d=\"M14 2H6a2 2 0 0 0-2 2v16a2 2 0 0 0 2 2h12a2 2 0 0 0 2-2V8z\"><\/path><polyline points=\"14 2 14 8 20 8\"><\/polyline><line x1=\"16\" y1=\"13\" x2=\"8\" y2=\"13\"><\/line><line x1=\"16\" y1=\"17\" x2=\"8\" y2=\"17\"><\/line><polyline points=\"10 9 9 9 8 9\"><\/polyline><\/svg>\n          Current execution\n        <\/div>\n        \n        <h3 id=\"step-title\" style=\"font-family: 'Outfit'; font-size: 1.15rem; margin-bottom: 0.5rem; font-weight: 700;\">Step 1: Initialization<\/h3>\n        <div id=\"step-desc\" class=\"step-desc\">\n          Initialize Disjoint Set (Union-Find) structures. Each vertex starts as its own component. Sort all edges by weight.\n        <\/div>\n\n        <div class=\"state-section\">\n          <div class=\"state-section-title\">Connected Components Partition<\/div>\n          <div class=\"badge-list\" id=\"components-container\">\n            <span class=\"comp-badge\" style=\"color:var(--comp-A);\">{A}<\/span>\n            <span class=\"comp-badge\" style=\"color:var(--comp-B);\">{B}<\/span>\n            <span class=\"comp-badge\" style=\"color:var(--comp-C);\">{C}<\/span>\n            <span class=\"comp-badge\" style=\"color:var(--comp-D);\">{D}<\/span>\n            <span class=\"comp-badge\" style=\"color:var(--comp-E);\">{E}<\/span>\n          <\/div>\n        <\/div>\n\n        <!-- MST Summary Block at card bottom -->\n        <div class=\"summary-bar\">\n          <div class=\"summary-item\">\n            <span class=\"summary-lbl\">MST weight<\/span>\n            <span class=\"summary-val mst-val\" id=\"mst-weight\">0<\/span>\n          <\/div>\n          <div class=\"summary-item\">\n            <span class=\"summary-lbl\">MST Edges Selected<\/span>\n            <div class=\"summary-box-list\" id=\"mst-edges-list\">\n              <span class=\"text-muted\" style=\"font-size:0.75rem;\">None<\/span>\n            <\/div>\n          <\/div>\n        <\/div>\n      <\/div>\n\n      <!-- Sorted Edges Side Checklist -->\n      <div class=\"panel-card\">\n        <div class=\"panel-title\">\n          <svg width=\"16\" height=\"16\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"2\"><line x1=\"8\" y1=\"6\" x2=\"21\" y2=\"6\"><\/line><line x1=\"8\" y1=\"12\" x2=\"21\" y2=\"12\"><\/line><line x1=\"8\" y1=\"18\" x2=\"21\" y2=\"18\"><\/line><line x1=\"3\" y1=\"6\" x2=\"3.01\" y2=\"6\"><\/line><line x1=\"3\" y1=\"12\" x2=\"3.01\" y2=\"12\"><\/line><line x1=\"3\" y1=\"18\" x2=\"3.01\" y2=\"18\"><\/line><\/svg>\n          Sorted Edges Queue\n        <\/div>\n        \n        <div class=\"edge-table\" id=\"edge-checklist\">\n          <!-- Populated by JS -->\n          <div class=\"edge-row unprocessed\" id=\"row-B-C\">\n            <span>1. <strong>B-C<\/strong> (weight 1)<\/span>\n            <span class=\"status-badge unprocessed\">Unprocessed<\/span>\n          <\/div>\n        <\/div>\n      <\/div>\n    <\/div>\n  <\/div>\n\n  <!-- Informative Section Footer -->\n  <div class=\"info-footer-grid\">\n    <div class=\"footer-card\">\n      <div class=\"footer-card-title\">\n        <svg width=\"16\" height=\"16\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"var(--color-mst)\" stroke-width=\"2\"><path d=\"M22 11.08V12a10 10 0 1 1-5.93-9.14\"><\/path><polyline points=\"22 4 12 14.01 9 11.01\"><\/polyline><\/svg>\n        Key Strengths\n      <\/div>\n      <ul class=\"info-list\">\n        <li>\n          <span class=\"bullet-ok\">\u2714<\/span>\n          <div><strong>Optimal for Sparse Graphs:<\/strong> Time complexity <span class=\"formula\">O(E log E)<\/span> makes it highly efficient when the edge count is low.<\/div>\n        <\/li>\n        <li>\n          <span class=\"bullet-ok\">\u2714<\/span>\n          <div><strong>Simple Union-Find Logic:<\/strong> Cycle detection takes nearly constant time <span class=\"formula\">O(\u03b1(V))<\/span> using path compression and union by rank.<\/div>\n        <\/li>\n        <li>\n          <span class=\"bullet-ok\">\u2714<\/span>\n          <div><strong>Disconnected Graphs:<\/strong> Can easily find Minimum Spanning Forests if the input graph is not fully connected.<\/div>\n        <\/li>\n      <\/ul>\n    <\/div>\n    \n    <div class=\"footer-card\">\n      <div class=\"footer-card-title\">\n        <svg width=\"16\" height=\"16\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"var(--color-skipped)\" stroke-width=\"2\"><circle cx=\"12\" cy=\"12\" r=\"10\"><\/circle><line x1=\"15\" y1=\"9\" x2=\"9\" y2=\"15\"><\/line><line x1=\"9\" y1=\"9\" x2=\"15\" y2=\"15\"><\/line><\/svg>\n        Limitations &amp; Complexity\n      <\/div>\n      <ul class=\"info-list\">\n        <li>\n          <span class=\"bullet-no\">\u2718<\/span>\n          <div><strong>Dense Graph Slowdown:<\/strong> In very dense graphs where <span class=\"formula\">E \u2248 V\u00b2<\/span>, Prim&#8217;s algorithm with a Fibonacci heap can outperform Kruskal&#8217;s.<\/div>\n        <\/li>\n        <li>\n          <span class=\"bullet-no\">\u2718<\/span>\n          <div><strong>Sorting Overhead:<\/strong> The sorting phase takes <span class=\"formula\">O(E log E)<\/span>, which dominates the overall execution time.<\/div>\n        <\/li>\n        <li>\n          <span class=\"bullet-no\">i<\/span>\n          <div><strong>Space Complexity:<\/strong> Needs <span class=\"formula\">O(V)<\/span> space for disjoint-set representatives and ranks, and <span class=\"formula\">O(E)<\/span> for storage.<\/div>\n        <\/li>\n      <\/ul>\n    <\/div>\n  <\/div>\n\n<\/div>\n\n<!-- Logic -->\n<script>\n  \/\/ Color palette for Union-Find representatives\n  const rootColors = {\n    \"A\": \"var(--comp-A)\",\n    \"B\": \"var(--comp-B)\",\n    \"C\": \"var(--comp-C)\",\n    \"D\": \"var(--comp-D)\",\n    \"E\": \"var(--comp-E)\"\n  };\n\n  \/\/ Edges sorted by weight (corrected list)\n  const sortedEdges = [\n    { id: \"B-C\", u: \"B\", v: \"C\", w: 1, text: \"B-C (weight 1)\" },\n    { id: \"A-C\", u: \"A\", v: \"C\", w: 2, text: \"A-C (weight 2)\" },\n    { id: \"D-E\", u: \"D\", v: \"E\", w: 2, text: \"D-E (weight 2)\" },\n    { id: \"A-B\", u: \"A\", v: \"B\", w: 4, text: \"A-B (weight 4)\" },\n    { id: \"B-D\", u: \"B\", v: \"D\", w: 5, text: \"B-D (weight 5)\" },\n    { id: \"B-E\", u: \"B\", v: \"E\", w: 6, text: \"B-E (weight 6)\" },\n    { id: \"C-D\", u: \"C\", v: \"D\", w: 8, text: \"C-D (weight 8)\" },\n    { id: \"C-E\", u: \"C\", v: \"E\", w: 10, text: \"C-E (weight 10)\" }\n  ];\n\n  \/\/ Simulation steps definition\n  const steps = [\n    {\n      title: \"Step 1: Initialization\",\n      desc: \"Initialize Disjoint Set (Union-Find). Every vertex is its own separate component: <span class='comp-badge' style='color:var(--comp-A); font-size:0.75rem; padding:0.1rem 0.3rem;'>{A}<\/span>, <span class='comp-badge' style='color:var(--comp-B); font-size:0.75rem; padding:0.1rem 0.3rem;'>{B}<\/span>, etc. Sort all edges in non-decreasing order of weight.\",\n      components: [[\"A\"], [\"B\"], [\"C\"], [\"D\"], [\"E\"]],\n      parent: { A: \"A\", B: \"B\", C: \"C\", D: \"D\", E: \"E\" },\n      root: { A: \"A\", B: \"B\", C: \"C\", D: \"D\", E: \"E\" },\n      mstWeight: 0,\n      activeEdge: null,\n      edgeStatuses: {\n        \"B-C\": \"unprocessed\", \"A-C\": \"unprocessed\", \"D-E\": \"unprocessed\", \"A-B\": \"unprocessed\",\n        \"B-D\": \"unprocessed\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: []\n    },\n    {\n      title: \"Step 2: Process Edge (B-C, Weight 1)\",\n      desc: \"Find representatives: <code>find(B) = B<\/code> and <code>find(C) = C<\/code>. Since they belong to different components, adding this edge does not create a cycle. <span class='text-mst'><strong>Add B-C to the MST<\/strong><\/span> and union components: <code>union(B, C)<\/code>.\",\n      components: [[\"A\"], [\"B\", \"C\"], [\"D\"], [\"E\"]],\n      parent: { A: \"A\", B: \"C\", C: \"C\", D: \"D\", E: \"E\" },\n      root: { A: \"A\", B: \"C\", C: \"C\", D: \"D\", E: \"E\" },\n      mstWeight: 1,\n      activeEdge: \"B-C\",\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"unprocessed\", \"D-E\": \"unprocessed\", \"A-B\": \"unprocessed\",\n        \"B-D\": \"unprocessed\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: [\"B-C (1)\"]\n    },\n    {\n      title: \"Step 3: Process Edge (A-C, Weight 2)\",\n      desc: \"Find representatives: <code>find(A) = A<\/code> and <code>find(C) = C<\/code>. Since they belong to different components, adding this edge does not create a cycle. <span class='text-mst'><strong>Add A-C to the MST<\/strong><\/span> and union components: <code>union(A, C)<\/code>.\",\n      components: [[\"A\", \"B\", \"C\"], [\"D\"], [\"E\"]],\n      parent: { A: \"C\", B: \"C\", C: \"C\", D: \"D\", E: \"E\" },\n      root: { A: \"C\", B: \"C\", C: \"C\", D: \"D\", E: \"E\" },\n      mstWeight: 3,\n      activeEdge: \"A-C\",\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"added\", \"D-E\": \"unprocessed\", \"A-B\": \"unprocessed\",\n        \"B-D\": \"unprocessed\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: [\"B-C (1)\", \"A-C (2)\"]\n    },\n    {\n      title: \"Step 4: Process Edge (D-E, Weight 2)\",\n      desc: \"Find representatives: <code>find(D) = D<\/code> and <code>find(E) = E<\/code>. Since they belong to different components, adding this edge does not create a cycle. <span class='text-mst'><strong>Add D-E to the MST<\/strong><\/span> and union components: <code>union(D, E)<\/code>.\",\n      components: [[\"A\", \"B\", \"C\"], [\"D\", \"E\"]],\n      parent: { A: \"C\", B: \"C\", C: \"C\", D: \"E\", E: \"E\" },\n      root: { A: \"C\", B: \"C\", C: \"C\", D: \"E\", E: \"E\" },\n      mstWeight: 5,\n      activeEdge: \"D-E\",\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"added\", \"D-E\": \"added\", \"A-B\": \"unprocessed\",\n        \"B-D\": \"unprocessed\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: [\"B-C (1)\", \"A-C (2)\", \"D-E (2)\"]\n    },\n    {\n      title: \"Step 5: Process Edge (A-B, Weight 4)\",\n      desc: \"Find representatives: <code>find(A) = C<\/code> and <code>find(B) = C<\/code>. Since they already belong to the same component, adding this edge <span class='text-skipped'><strong>would create a cycle (A-B-C-A)<\/strong><\/span>. We <span class='text-skipped'><strong>SKIP<\/strong><\/span> this edge.\",\n      components: [[\"A\", \"B\", \"C\"], [\"D\", \"E\"]],\n      parent: { A: \"C\", B: \"C\", C: \"C\", D: \"E\", E: \"E\" },\n      root: { A: \"C\", B: \"C\", C: \"C\", D: \"E\", E: \"E\" },\n      mstWeight: 5,\n      activeEdge: \"A-B\",\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"added\", \"D-E\": \"added\", \"A-B\": \"skipped\",\n        \"B-D\": \"unprocessed\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: [\"B-C (1)\", \"A-C (2)\", \"D-E (2)\"]\n    },\n    {\n      title: \"Step 6: Process Edge (B-D, Weight 5)\",\n      desc: \"Find representatives: <code>find(B) = C<\/code> and <code>find(D) = E<\/code>. Since they belong to different components, adding this edge does not create a cycle. <span class='text-mst'><strong>Add B-D to the MST<\/strong><\/span> and union components: <code>union(B, D)<\/code>. All vertices are now connected!\",\n      components: [[\"A\", \"B\", \"C\", \"D\", \"E\"]],\n      parent: { A: \"C\", B: \"C\", C: \"C\", D: \"C\", E: \"C\" },\n      root: { A: \"C\", B: \"C\", C: \"C\", D: \"C\", E: \"C\" },\n      mstWeight: 10,\n      activeEdge: \"B-D\",\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"added\", \"D-E\": \"added\", \"A-B\": \"skipped\",\n        \"B-D\": \"added\", \"B-E\": \"unprocessed\", \"C-D\": \"unprocessed\", \"C-E\": \"unprocessed\"\n      },\n      mstEdgesList: [\"B-C (1)\", \"A-C (2)\", \"D-E (2)\", \"B-D (5)\"]\n    },\n    {\n      title: \"Step 7: Final Result\",\n      desc: \"The Minimum Spanning Tree is complete! We have selected <code>V - 1 = 4<\/code> edges, connecting all 5 vertices. The remaining edges in the sorted queue are skipped because all vertices are in a single component. <strong>Total Weight: 10<\/strong>.\",\n      components: [[\"A\", \"B\", \"C\", \"D\", \"E\"]],\n      parent: { A: \"C\", B: \"C\", C: \"C\", D: \"C\", E: \"C\" },\n      root: { A: \"C\", B: \"C\", C: \"C\", D: \"C\", E: \"C\" },\n      mstWeight: 10,\n      activeEdge: null,\n      edgeStatuses: {\n        \"B-C\": \"added\", \"A-C\": \"added\", \"D-E\": \"added\", \"A-B\": \"skipped\",\n        \"B-D\": \"added\", \"B-E\": \"skipped\", \"C-D\": \"skipped\", \"C-E\": \"skipped\"\n      },\n      mstEdgesList: [\"B-C (1)\", \"A-C (2)\", \"D-E (2)\", \"B-D (5)\"]\n    }\n  ];\n\n  let currentStepIndex = 0;\n  let playTimer = null;\n  let playSpeed = 2000;\n\n  \/\/ Initialize UI on load\n  document.addEventListener(\"DOMContentLoaded\", () => {\n    buildEdgeChecklist();\n    goToStep(0);\n    \n    \/\/ Add Keyboard navigation shortcuts\n    window.addEventListener(\"keydown\", (e) => {\n      if (e.key === \"ArrowRight\") {\n        nextStep();\n      } else if (e.key === \"ArrowLeft\") {\n        prevStep();\n      }\n    });\n  });\n\n  \/\/ Theme Toggler\n  function toggleTheme() {\n    const widget = document.getElementById(\"kruskal-widget\");\n    const currentTheme = widget.getAttribute(\"data-theme\");\n    const newTheme = currentTheme === \"dark\" ? \"light\" : \"dark\";\n    \n    widget.setAttribute(\"data-theme\", newTheme);\n    \n    const themeText = document.getElementById(\"theme-text\");\n    const sunIcon = document.getElementById(\"theme-icon-sun\");\n    const moonIcon = document.getElementById(\"theme-icon-moon\");\n    \n    if (newTheme === \"light\") {\n      themeText.textContent = \"Dark Mode\";\n      sunIcon.style.display = \"inline\";\n      moonIcon.style.display = \"none\";\n    } else {\n      themeText.textContent = \"Light Mode\";\n      sunIcon.style.display = \"none\";\n      moonIcon.style.display = \"inline\";\n    }\n  }\n\n  \/\/ Build the list of sorted edges in side panel\n  function buildEdgeChecklist() {\n    const container = document.getElementById(\"edge-checklist\");\n    container.innerHTML = \"\";\n    sortedEdges.forEach((edge, index) => {\n      const row = document.createElement(\"div\");\n      row.className = \"edge-row unprocessed\";\n      row.id = `row-${edge.id}`;\n      row.innerHTML = `\n        <span>${index + 1}. <strong>${edge.u}-${edge.v}<\/strong>: weight ${edge.w}<\/span>\n        <span class=\"status-badge unprocessed\" id=\"status-${edge.id}\">Unprocessed<\/span>\n      `;\n      container.appendChild(row);\n    });\n  }\n\n  \/\/ Jump to specific step\n  function goToStep(index) {\n    if (index < 0 || index >= steps.length) return;\n    \n    const oldStepIndex = currentStepIndex;\n    currentStepIndex = index;\n    \n    \/\/ Update Slider & Label\n    document.getElementById(\"step-slider\").value = currentStepIndex;\n    document.getElementById(\"step-label\").textContent = `Step ${currentStepIndex + 1} \/ ${steps.length}`;\n    \n    \/\/ Disable\/Enable buttons\n    document.getElementById(\"btn-prev\").disabled = (currentStepIndex === 0);\n    document.getElementById(\"btn-next\").disabled = (currentStepIndex === steps.length - 1);\n    \n    const stepData = steps[currentStepIndex];\n    const prevStepData = oldStepIndex !== currentStepIndex ? steps[oldStepIndex] : null;\n\n    \/\/ Update Text details\n    document.getElementById(\"step-title\").textContent = stepData.title;\n    \n    const descDiv = document.getElementById(\"step-desc\");\n    descDiv.innerHTML = stepData.desc;\n    \n    \/\/ Update border color of description based on action\n    descDiv.className = \"step-desc\";\n    if (stepData.activeEdge) {\n      const status = stepData.edgeStatuses[stepData.activeEdge];\n      if (status === \"added\") descDiv.classList.add(\"mst-update\");\n      else if (status === \"skipped\") descDiv.classList.add(\"skip-update\");\n    } else if (currentStepIndex === steps.length - 1) {\n      descDiv.classList.add(\"mst-update\");\n    }\n\n    \/\/ Update MST Weight\n    document.getElementById(\"mst-weight\").textContent = stepData.mstWeight;\n\n    \/\/ Update MST list\n    const mstListContainer = document.getElementById(\"mst-edges-list\");\n    if (stepData.mstEdgesList.length === 0) {\n      mstListContainer.innerHTML = '<span class=\"text-muted\" style=\"font-size:0.75rem;\">None<\/span>';\n    } else {\n      mstListContainer.innerHTML = stepData.mstEdgesList.map(edge => `<span class=\"summary-edge-tag\">${edge}<\/span>`).join(\"\");\n    }\n\n    \/\/ Update Connected Components Visual Badge List\n    const compContainer = document.getElementById(\"components-container\");\n    compContainer.innerHTML = \"\";\n    stepData.components.forEach(comp => {\n      const rootRep = comp[0]; \/\/ first element acts as representative\n      const badge = document.createElement(\"span\");\n      badge.className = \"comp-badge\";\n      badge.style.color = rootColors[rootRep];\n      badge.textContent = `{${comp.join(\", \")}}`;\n      compContainer.appendChild(badge);\n    });\n\n    \/\/ Update Union-Find Table values with CSS highlight if updated\n    [\"A\", \"B\", \"C\", \"D\", \"E\"].forEach(node => {\n      const parentCell = document.getElementById(`parent-${node}`);\n      const rootCell = document.getElementById(`root-${node}`);\n      \n      const newParent = stepData.parent[node];\n      const newRoot = stepData.root[node];\n      \n      \/\/ Check updates for parent cell\n      if (prevStepData && prevStepData.parent[node] !== newParent) {\n        parentCell.classList.remove(\"updated-cell\");\n        void parentCell.offsetWidth; \/\/ trigger reflow\n        parentCell.classList.add(\"updated-cell\");\n      }\n      parentCell.textContent = newParent;\n      parentCell.style.color = rootColors[newParent];\n\n      \/\/ Check updates for root cell\n      if (prevStepData && prevStepData.root[node] !== newRoot) {\n        rootCell.classList.remove(\"updated-cell\");\n        void rootCell.offsetWidth; \/\/ trigger reflow\n        rootCell.classList.add(\"updated-cell\");\n      }\n      rootCell.textContent = newRoot;\n      rootCell.style.color = rootColors[newRoot];\n    });\n\n    \/\/ Update Node Circle borders to reflect component colors\n    [\"A\", \"B\", \"C\", \"D\", \"E\"].forEach(node => {\n      const circle = document.querySelector(`#node-${node} .node-circle`);\n      const rep = stepData.root[node];\n      const colorVal = rootColors[rep];\n      circle.style.stroke = colorVal;\n      \/\/ Add background tint of root\n      circle.style.fill = `rgba(${hexToRgb(colorVal)}, 0.12)`;\n    });\n\n    \/\/ Update Edge status classes in Checklist and Graph SVG\n    sortedEdges.forEach(edge => {\n      const row = document.getElementById(`row-${edge.id}`);\n      const badge = document.getElementById(`status-${edge.id}`);\n      const svgEdge = document.getElementById(`edge-${edge.id}`);\n      const svgLabel = document.getElementById(`weight-${edge.id}`);\n      \n      let status = stepData.edgeStatuses[edge.id];\n      \n      \/\/ Override status for currently processing active edge\n      if (stepData.activeEdge === edge.id) {\n        status = \"comparing\";\n      }\n\n      \/\/ Reset classes\n      row.className = \"edge-row\";\n      badge.className = \"status-badge\";\n      svgEdge.className.baseVal = \"edge\";\n      svgLabel.className.baseVal = \"edge-label\";\n\n      if (status === \"unprocessed\") {\n        row.classList.add(\"unprocessed\");\n        badge.classList.add(\"unprocessed\");\n        badge.textContent = \"Unprocessed\";\n        svgEdge.classList.add(\"unprocessed\");\n      } else if (status === \"comparing\") {\n        row.classList.add(\"comparing\");\n        badge.classList.add(\"comparing\");\n        badge.textContent = \"Checking...\";\n        svgEdge.classList.add(\"active\");\n        svgLabel.classList.add(\"active\");\n      } else if (status === \"added\") {\n        row.classList.add(\"added\");\n        badge.classList.add(\"added\");\n        badge.textContent = \"Added (MST)\";\n        svgEdge.classList.add(\"mst\");\n        svgLabel.classList.add(\"mst\");\n      } else if (status === \"skipped\") {\n        row.classList.add(\"skipped\");\n        badge.classList.add(\"skipped\");\n        badge.textContent = \"Skipped (Cycle)\";\n        svgEdge.classList.add(\"skipped\");\n        svgLabel.classList.add(\"skipped\");\n      }\n    });\n  }\n\n  \/\/ Helper function to extract RGB from hex variables for background alpha opacity\n  function hexToRgb(hexName) {\n    \/\/ Basic hardcoded mappings for our colors\n    if (hexName.includes(\"comp-A\")) return \"59, 130, 246\";  \/\/ Blue\n    if (hexName.includes(\"comp-B\")) return \"168, 85, 247\"; \/\/ Purple\n    if (hexName.includes(\"comp-C\")) return \"16, 185, 129\"; \/\/ Emerald\n    if (hexName.includes(\"comp-D\")) return \"249, 115, 22\";  \/\/ Orange\n    if (hexName.includes(\"comp-E\")) return \"236, 72, 153\";  \/\/ Pink\n    return \"100, 116, 139\";\n  }\n\n  \/\/ Play \/ Pause Logic\n  function togglePlay() {\n    if (playTimer) {\n      pauseVisualizer();\n    } else {\n      playVisualizer();\n    }\n  }\n\n  function playVisualizer() {\n    if (currentStepIndex === steps.length - 1) {\n      goToStep(0); \/\/ Loop back to start if finished\n    }\n    \n    document.getElementById(\"play-text\").textContent = \"Pause\";\n    \/\/ Pause Icon\n    document.getElementById(\"play-icon\").innerHTML = '<rect x=\"5\" y=\"4\" width=\"4\" height=\"16\"\/><rect x=\"15\" y=\"4\" width=\"4\" height=\"16\"\/>';\n    \n    playTimer = setInterval(() => {\n      if (currentStepIndex < steps.length - 1) {\n        goToStep(currentStepIndex + 1);\n      } else {\n        pauseVisualizer();\n      }\n    }, playSpeed);\n  }\n\n  function pauseVisualizer() {\n    if (playTimer) {\n      clearInterval(playTimer);\n      playTimer = null;\n    }\n    document.getElementById(\"play-text\").textContent = \"Play\";\n    \/\/ Play Icon\n    document.getElementById(\"play-icon\").innerHTML = '<polygon points=\"5,3 19,12 5,21\"\/>';\n  }\n\n  function nextStep() {\n    if (currentStepIndex < steps.length - 1) {\n      goToStep(currentStepIndex + 1);\n    } else {\n      pauseVisualizer();\n    }\n  }\n\n  \/\/ Keyboard and Click handlers\n  function prevStep() {\n    if (currentStepIndex > 0) {\n      goToStep(currentStepIndex - 1);\n    }\n  }\n\n  function resetVisualizer() {\n    pauseVisualizer();\n    goToStep(0);\n  }\n\n  function changeSpeed(val) {\n    playSpeed = parseInt(val);\n    if (playTimer) {\n      pauseVisualizer();\n      playVisualizer();\n    }\n  }\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Kruskal\u2019s Algorithm: A Greedy Approach to Minimum Spanning Trees Spanning trees are fundamental to network design, cluster analysis, and routing protocols. In this guide, we will break down Kruskal\u2019s Algorithm, one of the most elegant and widely-used greedy algorithms in computer science. Before moving to understanding more of Kruskal Algorithm, you should be aware of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-39","post","type-post","status-publish","format-standard","hentry","category-dsa"],"_links":{"self":[{"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/posts\/39","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algovelgo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=39"}],"version-history":[{"count":10,"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":50,"href":"https:\/\/algovelgo.com\/index.php?rest_route=\/wp\/v2\/posts\/39\/revisions\/50"}],"wp:attachment":[{"href":"https:\/\/algovelgo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algovelgo.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algovelgo.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}