Pseudo Code

Lección 4 de 9 del curso Algoritmo de Prim - Algoritmos de grafos de Coddy.

prim(n, edges):
   inTree[0] = true; todo lo demás falso
   total = 0
   repeat (n - 1) times:
      best = la arista de cruce (un extremo dentro, uno fuera) con el peso más pequeño
      if none exists: stop      # desconectado
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

Una arista (u, v, w) cruza el corte cuando inTree[u] y inTree[v] difieren.
Escanear todas las aristas en cada ronda para encontrar la arista de cruce más barata mantiene el código simple (no se necesita una cola de prioridad para grafos pequeños).

Pruébalo tú mismo

Esta lección no incluye un desafío de código.

Ponte 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 Prim - Algoritmos de grafos

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2