Componentes conexas. Método recursivo.


Bien, la segunda parte. Esta es mucho menos matemática que la anterior, mucho más visual e intuitiva. Sin embargo, para el tipo de grafos a los que está orientado este método, será mucho mas eficaz el de la última entrega, que sigue siendo intuitivo, aunque un pelín más complicado de programar. El tipo de grafos a los que está orientado son matrices binarias, tales como las del capítulo anterior. Cada punto puede estar conectado con los 8 ó 4 de alrededor. Nosotros lo haremos con ocho. Lo que hará será devolvernos una matriz con las componentes conexas numeradas. Por ejemplo, le pasamos esta matriz:

0   1   1   1   0   0   0
1   1   1   0   0   0   0
1   0   0   0   1   0   1
1   1   0   1   1   0   1
0   0   0   0   1   1   1
1   1   1   0   0   0   0
1   1   1   1   1   0   0

Y nos devuelve esta:

0   1   1   1   0   0   0
1   1   1   0   0   0   0
1   0   0   0   2   0   2
1   1   0   2   2   0   2
0   0   0   0   2   2   2
3   3   3   0   0   0   0
3   3   3   3   3   0   0

Bien, este método funcionará de la siguiente forma:

Crearemos una función que reciba la matriz. Esta función crea una matriz de ceros de igual tamaño. Esta función tendrá una variable que empiece en 1 y vaya subiendo. Recorrerá la matriz de casilla en casilla. Cuando llegue a una diferente de 0, le pasa esa casilla a la función recursiva, que se encarga de todo. Después le suma 1 a la variable de etiquetas y sigue recorriendo la matriz.

La función recursiva recibe la matriz de ceros, la matriz original, la etiqueta, y los índices de la casilla. En la casilla a rellenar, en la matriz original la pone a 0, y le pone la etiqueta a la misma casilla de la matriz de ceros. Después recorre  los 8 vecinos y se llama a si misma si encuentra alguno diferente de 0, pasándole la misma etiqueta.

Veámoslo con una matriz muy simple, tenemos a la izquierda la matriz original, y a la derecha la de ceros:

\begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 1 & 0 & 1\\  1 & 1 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Empieza recorriendo la primera fila hasta llegar a la última casilla, que es la única ocupada. Aquí salta a la función recursiva. Esta función borra la casilla de la matriz original y le pone la etiqueta a la de ceros, que en este momento es 1. Quedará así:

\begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 1 & 0 & 1\\  1 & 1 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Ahora busca sus vecinos en busca de otra casilla ocupada. Encuentra la de abajo, así que se llama a si misma con la misma etiqueta y en la nueva casilla. La borra de la original y le pone la etiqueta:

\begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 1 & 0 & 0\\  1 & 1 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 0 & 0 & 1\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Ahora busca de nuevo en busca de vecinos, pero en la matriz original ya no hay ningún 1 alrededor, así que la función recursiva acaba y volvemos a la función principal. Esta le suma 1 a la etiqueta, que ahora valdrá 2, y sigue buscando. Encontrará la casilla (2,2), así que salta a la función recursiva, esta la borra de la original y pone la etiqueta en la matriz de ceros:

\begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  1 & 1 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 2 & 0 & 1\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Ahora busca vecinos, encuentra la de abajo, así que vuelve a saltar, borra de la original y etiqueta a la matriz de ceros:

\begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  1 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 2 & 0 & 1\\  0 & 2 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Vuelve a buscar y encuentra la casilla de la izquierda, así que repite:

\begin{pmatrix}  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}  \begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 2 & 0 & 1\\  2 & 2 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

Vuelve a buscar, pero ya no hay vecinos, así que se acaba la función recursiva y sigue con la principal, que va recorriendo la matriz. Como ya no hay más unos, terminará de recorrerla y la función acabará. Nos devolverá la matriz de ceros, que ahora tiene las regiones de la matriz original numeradas.

\begin{pmatrix}  0 & 0 & 0 & 1\\  0 & 2 & 0 & 1\\  2 & 2 & 0 & 0\\  0 & 0 & 0 & 0  \end{pmatrix}

El código es muy sencillo, así que no lo explico mucho. La función principal: http://pastebin.com/ACfUC4fB

La función recursiva: http://pastebin.com/bMDiAGQb

La función recursiva puede parecer un poco liosa, pero no lo es. Lo que hace es, en las dos primeras lineas, borrar de la matriz original y meter en la de ceros la etiqueta (label). El resto es buscar vecinos, teniendo cuidado de no salirse de los límites de la matriz. Por ejemplo, antes de mirar si la casilla (x-1,y) está ocupada, se asegura de que x sea mayor que 1, si no mirará en x=0, y eso en matlab es estar fuera. Si lo haces con arrays en C, entonces tendrás que mirar que sea mayor que 0, y menor que el número de filas, para no salirte.

Ya está. Probemos con la matriz del principio del artículo:

>> matriz = [
> 0 1 1 1 0 0 0
> 1 1 1 0 0 0 0
> 1 0 0 0 1 0 1
> 1 1 0 1 1 0 1
> 0 0 0 0 1 1 1
> 1 1 1 0 0 0 0
> 1 1 1 1 1 0 0]
matriz =
0   1   1   1   0   0   0
1   1   1   0   0   0   0
1   0   0   0   1   0   1
1   1   0   1   1   0   1
0   0   0   0   1   1   1
1   1   1   0   0   0   0
1   1   1   1   1   0   0

Se la pasamos a nuestra función:

etiq = recurs(matriz)
etiq =
0   1   1   1   0   0   0
1   1   1   0   0   0   0
1   0   0   0   2   0   2
1   1   0   2   2   0   2
0   0   0   0   2   2   2
3   3   3   0   0   0   0
3   3   3   3   3   0   0

Ha funcionado bien.

Como veis, y como yo creo, el lenguaje Matlab es bastante sencillo. No creo que sea difícil pasar esto a cualquier otro lenguaje de programación. De todos modos, si tienes alguna dificultad en algún aspecto, no dudes en preguntar.

Un saludo.

P.D.: He subido los archivos de fuente aquí: http://neowriter.eshost.es/

Anuncios
Esta entrada fue publicada en Componentes conexas, Manuales, Manuales largos y etiquetada , , , , , , , , , , , , , , , , , . Guarda el enlace permanente.

Una respuesta a Componentes conexas. Método recursivo.

  1. Pingback: DUO | White-Hat Hacking

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s