← Volver a los ejercicios

Un recorrido por cada grupo

Cuántos grupos de vértices hay que no se alcanzan entre sí, y de qué tamaño es cada uno. El ciclo externo de la clase, con un contador adentro: cada componente que aparece se pinta de un color. El recorrido interno viene en sus dos formas, con pila y recursivo, y se puede cambiar de una a otra sin perder el grafo.

1. El grafo y la predicción

Entrada: un grafo no dirigido en lista de adyacencia.  Salida: la lista con el tamaño de cada componente conexo, en el orden en que el recorrido los descubre.

Grafo:
¿Cuántos componentes tiene?

2. Ejecute y mire los colores

Recorrido interno:
Pila: vacía
Tamaños: [ ]
Paso 0 de 0
Compare el contador de la línea 8 con el de la línea 7.

3. Una fila por componente

ComponenteArrancó enVérticesTamaño

4. Quién cuenta los componentes

¿Qué línea del programa decide que empieza un componente nuevo?

5. El costo

Con n vértices, m aristas y k componentes, ¿cuánto cuesta componentes(G)?
La marca es global. El recorrido que arranca en un componente no entra a los vértices de otro, así que los k recorridos se reparten los n vértices y las m aristas sin repetir ninguno.

6. La pila que no se ve

En la versión recursiva no hay ninguna lista pila. ¿Qué hace su trabajo?
Las dos versiones marcan, cuentan y pintan lo mismo. La diferencia está en dónde queda lo pendiente: en una lista que el programa maneja, o en la pila de llamadas que maneja el lenguaje, y esa segunda tiene un tope.

7. Para llevarse

Sin solución aquí. Modifique el programa para que devuelva, en vez de los tamaños, la lista grupo donde grupo[v] es el número del componente al que pertenece v. Con ella, ¿cómo se contesta en Θ(1) si dos vértices están conectados? ¿Y qué pasa con esa respuesta si después se agrega una arista?