← Volver a los ejercicios

Prim línea por línea

Se ejecuta prim paso a paso desde la raíz que se escoja, con extraer_minimo recorrido vértice por vértice. El contador de cada línea dice cuántas veces se ejecuta.

1. El grafo, la raíz y la predicción

Grafo:

Sobre cada vértice, clave/padre, con ∞ para INFTY y un guion para None. Verde: los que ya están en el árbol y las aristas de padre. Azul: el borde del árbol. Ámbar: la arista que se examina.

2. Ejecute el código

Paso 0 de 0
El contador de la línea 15 es la pasada completa de extraer_minimo: una por vértice, en cada vuelta del ciclo.

3. clave y padre

En ámbar, el vértice que acaba de entrar. En verde, la clave que acaba de bajar.

4. La misma corrida con cola de prioridad

Entran
Salen
Tachada, una pareja vieja. Sale de la cola y no hace nada, porque su vértice ya está en el árbol.

5. Para llevarse

En el grafo de ocho vértices, corra prim desde la raíz 7 y diga en qué puesto entra el vértice 1 y cuántas veces baja su clave. Después diga qué pasa con el contador de la línea 15 si el grafo conserva los mismos vértices y se le agregan cinco aristas.