Teniendo una gráfica, queremos encontrar o recorrer sus componentes conexas. Por ejemplo, suponiendo que los vértices en una gráfica representan países, y que las aristas unen a países del mismo continente que tienen frontera común, nos puede interesar saber cuantos continentes existen, saber cual continente tiene más países o asignarle alguna etiqueta a cada país.

Para encontrar las componentes conexas, primero marcamos todos los vértices como no visitados, y después elegimos al primero de ellos. A este vértice lo marcamos como perteneciente a la primera componente, y después marcamos a todos los que están conectados con el, y repetimos esto hasta que no encontremos algún vértice adyacente. En seguida, buscamos algún vértice que no haya sido visitado, lo marcamos como perteneciente a la segunda componte y marcamos todos los que estén interconectados. Esto lo repetimos hasta que ya no existan vértices sin marcar.

Para hacerlo de forma sistemática, podemos buscar cuales vértices no han sido marcados mediante una búsqueda lineal (con un for, por ejemplo) y cada ocasión que encontremos alguno, realizamos una búsqueda en profundidad. Podemos cambiar la búsqueda en profundidad por cualquier otra búsqueda exhaustiva en un árbol, pero generalmente es más sencillo de programar la primera.

Podemos imaginar el funcionamiento de este algoritmo como cuando utilizamos la cubeta en algún programa de dibujo (diseño). Empezamos en un punto predeterminado, y a partir de ahí nos expandemos coloreando todo hasta que lleguemos a los bordes de la imagen.




Solución: Recorremos todos los cuartos y cada que encontremos una pared, incrementamos un contador. El recorrido lo vamos a realizar mediante una búsqueda en profundidad. Un detalle que debemos considerar es que en el problema no se especifica si las dos entradas (las esquinas) están conectadas, por lo que existe la posibilidad de que existan dos componentes conexas distintas.





En las primeras cuatro líneas declaramos las variables a utilizar. Las variables i y j las utilizamos para los ciclos, n para el tamaño del laberinto, t para contar el total de paredes, l para guardar el laberinto y b para saber si ya visitamos un cuarto. Para no tener que revisar los casos especiales de las orillas, agregamos un contorno extra a los arreglos (comúnmente llamados “centinelas”).

En el procedimiento recorre (líneas 6 a la 21), visitamos el laberinto. Empezamos poniendo el cuarto actual como recorrido (línea 8). En las siguientes tres líneas revisamos si el cuarto a la derecha lo hemos visitado, y si no lo hemos hecho, revisamos si es un cuarto vacío o una pared. En el caso de que sea un cuarto, lo visitamos. En el caso de que sea una pared, la contamos. En las siguientes nueve líneas realizamos lo mismo que en las tres anteriores, pero para los cuartos de la izquierda, arriba y abajo.

La parte principal del código la encontramos entre las líneas 23 y 38. En la línea 24 leemos el tamaño del laberinto. Las siguientes dos líneas las utilizamos para inicializar los arreglos. En laberinto lo inicializamos como si fueran todas paredes (línea 25), y los cuartos los marcamos como visitables (línea 26). Entre las líneas 27 y 32 leemos el laberinto. Después inicializamos el total a cero (línea 33), y recorremos el laberinto a partir de la entrada (línea 34). Si no hemos visitado la salida, recorremos esta parte del laberinto (líneas 35 y 36). Por último, escribimos la salida (línea 37). Al total le restamos cuatro porque la entrada y la salida no tienen dos paredes cada uno, y lo multiplicamos por el área de cada pared.

Entrada:	5 ..... ...## ..#.. ..### .....
Desarrollo:	x  y   paredes  1  1;     2  2  1;     3  3  1;     4  4  1;     5  5  1;     7  5  2;     8  4  2;     9  3  2;    10  2  2;    10  1  2;    11  1  3;    12  2  3;    14  1  4;    16  1  5;    19  5  3;    21  5  4;    23  5  5;    26 9*(26-5)= 198
Salida:	198

Nota: En este ejemplo estamos contando las paredes al momento de entrar en el cuadro en lugar de cuando intentamos acceder a otro, por lo que los valores no corresponden a los de la variable t.

Lenguaje	Fecha	Tiempos [s]				Memoria [Kb]
		Ejecución	Mejor	Mediana	Peor
Pascal	26-Abr-2006	0.001	0.001	0.015	0.125	142
C	27-Abr-2006	0.001				146

Valladolid: