Laboratoire Python Interactif

Kruskal's MST

Le playground s'exécute automatiquement au chargement. Cliquez sur Exécuter mon code pour tracer votre propre Python — chaque étape animée en direct.

Expliquer·Ligne par ligne

Rejouer·Étape par étape

Défi·Indices guidés

XP·...

Pipeline de Flux de Données

mastery Parcours

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

Expliquer

Line 2

Initialize Union-Find

Pourquoi cette approche ?

Each vertex starts as its own parent — every node is its own component initially. parent[i] = i means 'i is a root.'

Structured Explanation

Overview

L'algorithme de Kruskal construit un arbre couvrant minimum en ajoutant les arêtes de poids le plus faible qui ne créent pas de cycle.

Analogy

Comme construire un réseau ferroviaire à moindre coût — ajoute toujours la ligne la moins chère qui connecte deux villes non encore reliées.

Step-by-step

Trie toutes les arêtes par poids
Pour chaque arête (de la plus légère à la plus lourde)
Si elle ne crée pas de cycle, ajoute-la à l'ACM
Utilise Union-Find pour vérifier/prévenir les cycles

Visual

Arêtes triées: (1-2,1),(2-3,3),(1-3,4),(3-4,2) Ajoute 1-2, 2-3, 3-4: ACM={1-2,2-3,3-4}

Common mistakes

Oublier de trier les arêtes d'abord
Union-Find sans compression de chemin (trop lent)

Practice questions

Trouve l'ACM d'un graphe de réseau
Compare avec l'algorithme de Prim sur des graphes denses

Time

O(E log E)

Space

O(V)

Complexité

Temps

O(E log E)

Espace

O(V)

Aperçu de la Complexité

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8plage 1-20

POUR N = 8

Complexité	Opérations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Défi

Trouvez MST des arêtes: (A-B,4), (A-C,2), (B-C,1), (B-D,5), (C-D,8).

Indice

Triez les arêtes par poids. Utilisez Union-Find pour détecter les cycles.

Studio de Code

Kruskal's MST

Monaco Prêt

Python Prêt

lesson.pyline 2

Loading editor...

Console de Sortie

3 lines

❯ [(1, 2, 1)]

❯ [(1, 2, 1), (1, 3, 2)]

❯ [(1, 2, 1), (1, 3, 2), (0, 2, 3)]

Applications du Monde Réel

1

Network design

2

Circuit design

3

Clustering

4

Road planning

Comments

Loading comments...