.. _sphx_glr_api_gallery_graph_theory_spanning_tree:

Minimum spanning tree
-----------------------

Kruskal's (scipy) vs. Prim's (hand-rolled) MST.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Both algorithms find the same minimum spanning tree (same total weight) via very different strategies: Kruskal grows a forest by globally cheapest edge, Prim grows a single tree by locally cheapest edge.">

.. only:: html

  .. image:: /api/gallery/graph_theory/spanning_tree/images/thumb/sphx_glr_plot_01_kruskal_vs_prim_thumb.png
    :alt:

  :doc:`/api/gallery/graph_theory/spanning_tree/plot_01_kruskal_vs_prim`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Kruskal's vs. Prim's minimum spanning tree</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Counts spanning trees with a single determinant of the reduced Laplacian, and checks the count by brute-force enumeration of edge subsets on a small graph.">

.. only:: html

  .. image:: /api/gallery/graph_theory/spanning_tree/images/thumb/sphx_glr_plot_02_matrix_tree_theorem_thumb.png
    :alt:

  :doc:`/api/gallery/graph_theory/spanning_tree/plot_02_matrix_tree_theorem`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Kirchhoff's matrix-tree theorem</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/graph_theory/spanning_tree/plot_01_kruskal_vs_prim
   /api/gallery/graph_theory/spanning_tree/plot_02_matrix_tree_theorem