He escrito un código que compruebe si un grafo es o no conexo a partir de la matriz de adherencia del grafo. Creo que funciona, he hecho algunos ejemplos y parece que sí; adjunto unos gráficos. Supongo que debe de ser válido para otros. Pero me gustaría saber si a alguien se le ocurren contra-ejemplos, o si quiere exponer (puede ser por privado) una matriz de adherencia de un grafo (claro, yo los ejemplos que he hecho son a partir de grafos de los que conozco su representación gráfica en papel) para ver si funciona. Pero me gustaría probar con un grafo del que no conozca su representación gráfica en papel, sino solo su matriz de adherencia.
Pero sobre todo querría opiniones sobre el código, posibles fallos, y posibles mejoras. Solo opiniones generales, pseudocódigo quizá..., no hace falta código explícito; tampoco es para volver a escribirlo, que no tengo intención (salvo que vea fallos serios), sino para ver por dónde van los tiros.
Doy una idea general de cómo lo he hecho, luego expongo el código y luego pregunto las cosas que más me interesan.
La idea que se me ha ocurrido es algo parecido a "fuerza bruta". Se trata de recorrer todos los nodos que se pueda, a partir del primero. A partir del nodo inicial del grafo voy recorriendo un camino hasta que llega un nodo en el que no puedo ir más allá, doy marcha atrás y busco otro nodo para proseguir... y así sucesívamente. Voy yendo hacia adelante-atrás-adelante-atrás... Conforme voy agotando caminos posibles voy volviendo hacia atrás cada vez más, hasta que llega un punto en el que vuelvo al nodo de salida -después de haber ido explorando todos los caminos posibles-. En ese momento en el que he vuelto al nodo de partida veo si existe algún nodo al que no he llegado. Si existe es que el grafo es no conexo, ya que de haber habido un camino para llegar hasta él lo habría recorrido. Si no existen nodos sin visitar es que he llegado a todos y el grafo es conexo.
Ahora el código que he escrito y algunos ejemplos que he usado.
// Calcula si un grafo es conexo o no
#include <stdio.h>
#include <stdlib.h>
#define ORDEN_MATR (num_nodos * num_nodos)
void intro_grafo (int num_nodos, int ** matr_adher);
void procesa_grafo (int num_nodos, int nodo_actual, char * estado_nodo, int * camino, int posicion, char sentido, int ** matr_adher);
char es_conexo (int num_nodos, char * estado_nodo); // =0 si existe algun estado_nodo [i] == 0 ; =1 en caso contrario
int main ()
{
int num_nodos; // Nº de nodos del grafo
int ** matr_adher; // Matriz de adherencia del grafo
int nodo_actual; // El que se está procesando en un momento dado
char * estado_nodo; // 1 - si ya se ha pasado por él al menos una vez; 0 - en caso contrario
int * camino; // Guarda los nodos que se van recorriendo
int posicion; // subindice del arreglo camino [] que corresponde a nodo_actual
char sentido; // 1 si se va avanzando hacia nodo no visitado; 0 - si se va retrocediendo a nodo ya visitado
int i, j;
printf ("Introducir no. de nodos del grafo: "); scanf ("%d", &num_nodos
); printf ("el numero es: %d\n", num_nodos
); // Declara arreglos
matr_adher
= (int **) malloc ( ORDEN_MATR
* sizeof (int *) ); // Filas for ( i=0; i < num_nodos; i++ )
{
matr_adher
[i
] = (int *) malloc ( num_nodos
* sizeof (int) ); // Columnas }
estado_nodo
= (char *) malloc ( num_nodos
* sizeof (char *) ); camino
= (int *) malloc ( num_nodos
* sizeof (int *) );
// Inicializa variables
for (i = 0; i < num_nodos; i++)
for (j = 0; j < num_nodos; j++)
matr_adher [i][j] = 0; // Por defecto ningun nodo esta conectado con nigun otro
for (i = 0; i < num_nodos; i++)
estado_nodo [i] = 0; // Al inicio no se ha visitado ningun nodo
sentido = 1;
posicion = 0;
nodo_actual = 0;
camino [0] = 0;
// Ejecucion
intro_grafo (num_nodos, matr_adher);
procesa_grafo (num_nodos, nodo_actual, estado_nodo, camino, posicion, sentido, matr_adher);
if ( es_conexo (num_nodos, estado_nodo) )
printf ("El grafo es conexo\n"); else
printf ("El grafo NO es conexo\n");
return 0;
}
void intro_grafo (int num_nodos, int ** matr_adher)
{
int nodo1, nodo2, peso;
printf ("Introducir conexiones y pesos entre nodos en la forma:\n"); printf ("nudo inicial... nudo final... peso conexion\n\n"); printf ("No es necesario introducir conexiones reciprocas, la conexion i-j automaticamente es = a la j-i\n"); printf ("Una nueva conexion i-j actualiza a la anterior si existiera\n"); printf ("para finalizar el grafo introduzcir nudo incial = 0 y nudo final = 0\n\n"); for (;;)
{
if (nodo1 == 0 && nodo2 == 0)
return;
else
{
if (nodo1 != nodo2)
{
matr_adher [nodo1][nodo2] = peso;
matr_adher [nodo2][nodo1] = peso;
}
}
}
}
void procesa_grafo (int num_nodos, int nodo_actual, char * estado_nodo, int * camino, int posicion, char sentido, int ** matr_adher)
{
int j;
printf ("\nfuncion procesa_grafo\n"); // SOLO PARA DEPURACION DEL PROGRAMA - BORAR printf ("nodo actual: %d\n", nodo_actual
); // SOLO PARA DEPURACION DEL PROGRAMA - BORAR estado_nodo [nodo_actual] = 1;
if ( (nodo_actual == 0) && (sentido == 0) )
return;
for (j = 0; j < num_nodos; j++)
if ( (matr_adher [nodo_actual][j] != 0) && (estado_nodo[j] == 0) )
{
posicion += 1; // Recorre la fila de la matriz del nodo en proceso hasta encontrar
camino [posicion] = j; // una conexión con un nodo que no hay sido visitado anteriormente,
sentido = 1; // si lo encuentra cambia el control del proceso a ese nodo
procesa_grafo(num_nodos, j, estado_nodo, camino, posicion, sentido, matr_adher);
}
posicion -=1; // Caso de recorrer toda la fila y no encontrar un nodo en avance
sentido = 0; // retrocede al nodo anterior y cambial el control del proceso a ese punto
procesa_grafo (num_nodos, camino [posicion], estado_nodo, camino, posicion, sentido, matr_adher);
}
char es_conexo (int num_nodos, char * estado_nodo)
{
int i;
for (i = 0; i < num_nodos; i++)
if ( estado_nodo [i] == 0 )
return 0;
return 1;
}
Algunos ejemplo que he hecho
Algunas consideraciones:
- He considerado que un nodo no puede estar conectado consigo mismo; para saber si los nodos están conectados entre sí no hace falta, y estorba para el algoritmo.
- También he considerado solamente grafos en los cuáles los nodos están conectados en ambas direcciones: si se puede ir desde a hacia b, entonces también se puede ir desde b hacia a. (Creo que existen grafos en los cuáles puede haber trayectorias en un sentido pero no en el contrario).
- El peso de la conexión únicamente es útil para saber si dos nodos están conectados (==0 SI // !=0 NO), daría igual que fuesen sencillamente 1 ó 0. He dejado cualuier entero solamente por generalidad de la función de entrada de datos (no se trata de calcular longitudes mínimas o máximas de distintos caminos). Incluso podrían ser negativos ya que el programa solo considera si son o no igual a cero.
- He utilizado un arreglo (
camino []) y una variable (
posicion) para ir recorriendo la malla. Aunque creo que se podría utilizar una
pila LIFO y push-pop).
Defectos que ya veo:
- Si el nodo 0 está aislado el programa se pierde. Se podría corregir fácilmente haciendo que antes de comenzar a procesar se comprobara que la fila 0 de la matriz no es todo ceros; pero es trivial y no merece la pena; no afecta al algoritmo.
- He visto -a través de las líneas 90 y 91 que están solamente para depuración- que el algoritmo pasa varias veces por nudos que no haría falta (no afecta a la eficacia del código pero sí a la eficiencia del mismo: retardo). Veo que ésto es así por comenzar siempre el análisis de cada nuevo nodo (fila) desde cero (línea 96) en lugar de hacerlo desde el último nodo (columna) que se visitó a partir del nodo_actual. Pero no estoy muy seguro de cómo corregirlo; se me ocurre tener otro arreglo similar a camino [] en el cuál se anote ese nº de columna y comenzar el bucle de la línea 96 en ese lugar en vez de cero. No lo he hecho porque, bueno, lo que me importa es más bien que la idea general funcione, ya que no se trata de una aplicación práctica. Además añadiría más argumentos a la función procesa_grafo, que ya tiene bastantes.
Entonces:
- ¿Algún error de bulto? ¿Fallos, ejemplos de grafos que hagan que claramente el algoritmo no funcione...?
- ¿Alguna idea para corregir el bucle de la línea 96 y que no empiece desde cero?
- ¿Se mejoraría la eficiencia del programa usando una pila en lugar del arreglo y la posición?
- Y lo principal: ¿existiría otro tipo de algoritmo que no fuera recorrer todos los caminos posibles?; no sé, algo de tipo matemático, alguna propiedad matemática de la matriz de adherencia, algún método que use de expresiones matemáticas, en lugar de un algoritmo de recorrido paso a paso, que determine si el grafo es conexo o no. O en caso de algorimo de recorrido, ¿otra forma de hacer el recorrido que sea más eficiente?
- Por último: ¿alguna manera de programar más elegante (o eficaz) sin usar una
función recursiva. Tengo entendido que
los goto, las variables globales y la recursividad (por este orden) no son muy bienvenidas por los programadores ( al menos en C); y si se puede escribir un código más acorde a los usos habituales o deseables en programación, pues bienvenidos sean consejos.
Gracias de antemano por las respuestas.
Mostrar Mensajes
).
