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
Componente
Arrancó en
Vértices
Tamañ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?