El recorrido que arranca dentro de un componente lo entrega
entero y no se sale de él, porque ninguna arista cruza de un componente a
otro. El algoritmo es eso repetido: se arranca de nuevo desde el primer
vértice que quedó sin marcar. Aquí se ve la lista actual
llenándose y el color del componente ganando vértices.
Entrada: un grafo no dirigido en lista de adyacencia. Salida: la lista de componentes, cada uno como lista de vértices.
| Componente | Arranca en | Vértices, en orden de visita | Tamaño |
|---|
Sin solución aquí. En el grafo de nueve vértices, invierta el orden de las listas de adyacencia (que cada vecino aparezca de mayor a menor) y ejecute a mano la versión recursiva. Diga qué componente sale primero, en qué orden quedan sus vértices, y qué parte del resultado no se movió. Después agregue la arista 3–8 y diga cuántos componentes quedan.