Pseudo Code
Lección 4 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
kruskal(n, edges):
parent[i] = i for all i # cada vértice es su propio conjunto
total = 0
repeat until all edges considered:
pick the unused edge (u, v, w) with the smallest w
ru = find(u); rv = find(v)
if ru != rv: # sin ciclo
parent[ru] = rv # unión
total += w
return total
find(x):
while parent[x] != x: x = parent[x]
return x- Elegir la arista no utilizada más pequeña en cada ronda (selección mínima) evita la necesidad de una ordenación por separado.
- find recorre hasta la raíz; union es una asignación única de una raíz a la otra.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Esta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Kruskal - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)