Kruskal

[EN]
Implementation of Kruskal's algorithm

Kruskal is an algorithm that looks for the minimum weight coverage tree in a graph.

[FR]
Implémentation de l'algorithme de Kruskal

Kruskal est un algorithme qui recherche l'arbre couvrant de poids minimum dans un graphe.

Explanation

• English
• Français

Pre-requisites

Before starting, please make sure you have installed:

• python v3

Installation

# Download the repository
git clone https://github.com/coursecomputer/kruskal.git

Usage

CLI:

python3 -m unittest discover

CODE:

from source.graph import Graph

graph = Graph({
  "A": { "B": 3, "C": 6 },
  "B": { "A": 3, "C": 8 },
  "C": { "A": 6, "B": 8 },
})

graph.kruskal()
# [
#   ("A", "B", 3),
#   ("A", "C", 6),
# ]

Links

• https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
• https://en.wikipedia.org/wiki/Disjoint-set_data_structure
• https://www.youtube.com/watch?v=wU6udHRIkcc&feature=youtu.be (Abdul Bari - 1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find)