Menu
Coddy logo textTech

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.

quiz iconPonte a prueba

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