← Volver a los ejercicios

Un recorrido por componente

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.

1. El grafo y la predicción

Entrada: un grafo no dirigido en lista de adyacencia.  Salida: la lista de componentes, cada uno como lista de vértices.

Grafo:
¿Cuántos componentes conexos tiene?

2. Ejecute, con la versión que quiera

Recorrido:
Componente abierto: (ninguno abierto)
Pendientes: vacía
Devuelve: [ ]
Paso 0 de 0
Cada componente estrena color. La arista azul es la que se está mirando; se pone verde cuando lleva a un vértice sin marcar.

3. Una fila por componente

ComponenteArranca enVértices, en orden de visitaTamaño

4. Qué cambia entre las tres versiones

Corra las tres sobre el mismo grafo. ¿En qué se diferencian las salidas?

5. Para llevarse

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.