Minimum Spanning Tree ======================================== A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component. A Sample Question ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ .. code-block:: none As a network engineer, your task is to establish a network cabling system connecting four villages to provide them with internet access. Each village is assigned an ID from 1 to 4. The distances between the villages are given as follows: Village 1 to Village 3: 3 units Village 3 to Village 4: 2 units Village 4 to Village 2: 10 units Village 1 to Village 2: 24 units Village 1 to Village 4: 20 units Your objective is to determine the minimum total length of cable required to connect all four villages so that every village has internet access. Write a function that computes this minimal total cable length, ensuring that the network spans all villages without any isolations. [3]--2--[4] | / \ | / \ 3 20 10 | / \ | / \ [1]-----24-----[2] Consider the provided distances as a weighted graph where the villages are nodes, and the cables are edges with weights representing the distances. Your function should implement an algorithm to find the minimum spanning tree of this graph, which corresponds to the optimal configuration of cables with the minimum total length. Prim Algorithm ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex. Prim algorithm is very similar to dijkstra algorithm and is even simpler. .. figure:: mst_prim.png :align: center :name: prim BFS + Priority Queue ordered by edge weight .. literalinclude:: mst.h :linenos: :lines: 40-62 :language: c++ .. code-block:: none :caption: priority(u) = edge_weight(u) +---+ +---+ +---+ | s | ========> | u | -------> | t | +---+ +---+ +---+ .. only:: html - `Prims vs Dijkstra algorithm | MST vs SSSP `_ .. _Kruskal Algorithm: Kruskal Algorithm ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest. .. figure:: mst_kruskal.png :align: center :name: kruskal Union-Find starting with smallest available edges .. literalinclude:: mst.h :linenos: :lines: 14-30 :language: c++ :emphasize-lines: 6, 10, 12 The union-find data structure used in line 6 is defined at :numref:`Disjoint Set Union Find`.