Un algoritmo para calcular si un grafo es conexo o no

[fzp]

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.

Código (c) [Seleccionar] Expandir

// 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 (;;)
{
printf ("Nodo inicial: ");
scanf ("%d", &nodo1);
printf ("Nodo final: ");
scanf ("%d", &nodo2);
if (nodo1 == 0 && nodo2 == 0)
return;
else
{
printf ("Peso conexion: ");
scanf ("%d", &peso);
if (nodo1 != nodo2)
{
matr_adher [nodo1][nodo2] = peso;
matr_adher [nodo2][nodo1] = peso;
}
printf ("\n");
}
}
}

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.

[Serapis]

Se pueden ahcer muchos comentarios... permíteme extenderme, por que si no es casi preferible no decir nada.

- De entrada, como ejercicio está bien... la entrada de datos a petición uno por uno, pero lo ideal es que el programa acepte como entrada un string, que en sí mismo ya contenga todo el grafo y que tu programa lo desguace...
Digamos una función llamada SetDatos o Inicializacion que devuelva un buleano si el grafo está 'bien formado'. El string podría ser incluso la ruta de un fichero de texto, del que leer el grafo, incluso (es lo preferible) la misma función contener ambos parámetros, y ser procesada la primera entrada no nula entre ambos parámetros (es decir da preferencia al parámetro a la izquierda). Internamente el programa debiera mantener guardado los datos del grafo, así como si ha sido validado, para que una posterior llamada ('Procesar'), parta ya con la seguridad de que hay un grafo entrado y correcto merced a esa validacion. algo así...

Código [Seleccionar] Expandir


buleano Validado

buleano = Inicializar(string grafo, string path)
    si (grafo.length =0)
        si (path.length >0)
            grafo = LeerFile(Path)
        fin si
    fin si

    Si (grafo.length >0)
        validado = ValidarGrafo(grafo)
    sino
        validado = false
    fin si

    devolver validado
fin funcion

buleano = funcion Procesar(entero accion, otros parametros que fueren precisos)
   si (validado = TRUE)
        seleccion de accion
             accion = 1 ... invocar funcion1

             accion = x ... invocar funcionx
        fin seleccion
   sino
        mensaje "Actualmente no hay ningun grafo validado, debe ingresar uno antes de poder procesarlo..."
        devolver false
    fin si
fin funcion


- Como se ve al final del pseudocodigo previo, una vez que el grafo ha sido validado, se puede invocar ser procesado bajo diferentes peticiones, reflejado bajo el parámetro 'accion', una acción podría ser precisamente esa de '¿es un grafo conexo?'... en cuyo caso se invoca a la función que realiza esa averiguación.

- Desde un punto de vista puramente matemático, la matriz de adyacencia (no de 'adherencia') es muy útil, pero en un sistema informático, especialmente cuando un grafo vaya a ser grande o enorme, puede no ser muy útil del todo o un auténtico lastre.
Imagina un grafo de 100 nodos... 100x100 = 10.000 es decir tendrías que rellenar 10.000 casillas a mano, al estar hablando de un ejercicio donde tu mismo creas la entrada... y solo estamos hablando de 100 nodos... ¿qué, si fuera un grafo de 1.000 nodos (rellenarías una tabla de 1 millón de datos)?.
Ahondando más en el tema.... supongamos que el grafo ha de contener más propiedades que meramente a qué nodo está conectado (y veo que has usado un peso), pero pongamos que tienes más datos asociados que haya que procesar... cómo reflejarías en esa tabla cada uno de esos nuevos datos, más aún aunque no es complicado resolverlo dejando más espacio para rellenar datos, no aumentaría eso la cantidad de datos a rellenar aumentando el problema descrito en el párrafgo anterior?.

Hace alguna semanas, hice un grafo relacionado con sílabas... tenía aproximadamente (por pura casualidad) unos 100 nodos. Debe notarse como cada nodo solo referencia a los nodos a los que está conectado directamente, resulta absurdo rellenar las referencias de los nodos a los que no conecta. Se puede ver que aunque el listado todavía sea largo, es perfectamente asumible y además se puede guardar en un fichero, donde resultará cómodo de editar y guardar cambios.
Puedes mirar dicho ejemplo en el siguiente enlace:
https://foro.elhacker.net/hacking/diccionario_de_fuerza_bruta_tipo_v2-t510911.0.html;msg2253267#msg2253267
En el ejemplo presente en dicho enlace, se hace eco de una forma resumida, lo que acorta mucho más el texto redactado, si bien luego en memoria (al validar) debe expandirse.
Básicamente hice uso de algún tipo de macro, tal que ciertas apariciones repetitivas (y largas) se suplantan (en diseño), por una referecnia, y para reconocelro se trata como una 'directiva' (un nodo que debe tener un tratamiento especial previo).
En ejecución podría mantenerse también tal directiva, como un nodo de acceso, pero con cada nodo visitado, exigiría una comprobación de si es o no una directiva y entonces sería más lento... luego, uno debiera decidir si prima el ahorro de memoria o la velocidad de cálculo, y en base a ello decidir si expandir (cada caso) al validar o (solo el caso presente) al calcular a medida que aparecen...
Aún así, hay casos donde usar una forma canónica (la tabla de adyacencia), es deseable. Cada uno acertadamente debe comprender cuando se da tal caso.


- Lógicamente debes establecer un formato, una notación que seguir, y que tu función 'ValidarGrafo' debe interpretar y ser capaz de construir un array de un tipo de estructura (a partir del texto redactado en dicho formato).
Es esa estructura la que debe contener los diversos campos (propiedades), que cada nodo debe retener, así la complejidad de los datos, no se ve asfixiada por la entrada de datos que se intenta reflejar en una tabla cuadrada, que o se introduce manuamente uno a uno cada dato o un enorme fichero del que la mayor parte (probablemente) sean datos desechables, para los que ni siquiera haga falta guardarlos en parte alguna (cuando el programa tenga que operar).

- Por supuesto, como primera aproximación a la programación de grafos es más que adecuado empezar con una matriz de adyacencia, sobretodo para tomar confianza.
Nota al respecto que en cualquier caso, la iteración explora los nodos accesibles a uno dado (hijos, los directamente conectados) , y el acceso a un nodo (para luego recorrer sus 'hijos') obliga a la recursión. Son los bucles imprescindibles para recorrer un grafo. Y hay que notar que ni siquiera se necesita generar en memoria un grafo o un árbol, el recorrido lo va haciendo sobre la marcha, por ello la cantidad de memoria conumida mientras se ejecuta suele ser mínima, independientemente del tamaño del grafo.

- Tampoco resulta muy útil, más allá del ejercicio que supone, determinar si un grafo es conexo.
Aunque matemáticamente un grafo admite varias ramas, un grafo debe considerarse como un array de ramas, siendo cada rama, ni más ni menos que un grafo (el nombre de 'rama' solo tiene aquí un propósito diferenciador de la ubicación de una raíz existente pero no yacente)...
Por ejemplo, en tu grafo ese de la primera imagen (abajo a la izquierda), tienes un grafo no conexo... pero a nivel informático, no es aceptable tener un grafo a cuyas ramas no son accesibles. En determinados diseños eso equivale a decir que son datos erróneos o bien superfluos (y que por tanto pueden eliminarse)... pero a menudo lo que sucede es que falta una conexión de nivel mayor que no está presente, pero que sensiblemente existe.... luego ese grafo debería formatearse bajo un nuevo nodo que accede a sendos subgrafos.
Tienes por un lado la rama: 0-1-2-3-4-5 y por otro la rama 6-7, puede verse el conjunto como formado un nodo raíz llamado 8 que conecta a ambas ramas.
Técnicamente al hacer esto, debe asumirse la responsabilidad de decidir como se conectan al nodo 8, cada rama... solo a un nodo o a cada nodo de dicha rama?. La respuesta debe ser arrojada según el contexto del problema, pero tratándose de un ejercicio cualquier valor aleatorio puede valer.

- Por lo mismo, usar números como identificador de cada nodo, una vez más matemáticamente puede ser cómodo, pero de cara a una representación humana más comprensible es preferible asignarles un string... aunque solo sea una letra...
A-B-C-D-E... y mejor si son nombres largos cuando son ejemplos. Mientras desarrollas y pruebas el programa será más fácil no confundir nombres irrelevantes, como "1" o "J", usando por ejemplo Leon-Bilbao-Cadiz-Granada-Madrid, resultan más útil en dicho punto.
Lógicamente cuando el grafo es validado, será un índice en el array el que lo referencie, y puede optarse por dejar el nombre 'original' en la estructura asociada a cada nodo, más que nada por que la salida de datos, a menudo es conveniente devolver justamente esos nombres (que son más relevantes y nos aportan una información menos abstracta) que meramente su índice. El indice para procesado, y el nombre para el tratamiento humano (visualizar, comprobar).

Así por ejemplo, el grafo ese que refiero (de la primera imagen, abajo a la izquierda), yo lo describiría así:

Código [Seleccionar] Expandir


// nota: al poner 'conectado a' debe entenderse 'directamente conectado a'

R = A|G      //un nodo raíz 8, no presente conecta a cada rama del grafo (por no estar conectadas). Aquí se asume que conecta a los nodos 0 y 6 solamente.
A = B|F    // el nodo 0 solo está conectado a los nodos 1 y 5.
B= A|C|F  // el nodo 1 está conectado a los nodos 0, 2 y 5.
C= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5.
D= C|E|F  // el nodo 3 está conectado a los nodos 3,5 y 5.
E= D|F  // el nodo 5 está conectado a los nodos 4 y 5
F= A|B|C|D|E  // el nodo 5 está conectado al resto de nodos (de esta rama).

G= H  // el nodo 6 está conectado al nodo 7
H= G  // el nodo 7 está conectado al nodo 6

Como se puede ver (sin los comentarios), esto es mucho más breve que una matriz de adyacencia y describe exactamente el mismo grafo (he omitido el peso entre los nodos, para una primera aproximación a esta notación).

Nota además como el grado siendo no dirigido (originalmente), al ser un grafo con dos ramas no conexas, lo hemos convertido en un grafo dirigido, tal que desde una rama no es posible regresar a la raíz y seguir por la otra rama, pero en cambio cada rama supone (sigue siendo) un grafo no dirigido. Así este esquema cumple y completa la idea perseguida de grafo no conexo. Cuando se acceda a la primera rama, no conecta con la segunda y vicerversa. Siguen siendo ramas aisladas, pero ahora si forman un grafo 'tratable' (sus datos son accesbiles desde una raíz que puede ser tratado en bucle si se precisa desde la función principal que deriva a la de recorrido).

No es obligatorio que cada rama deba ser un grafo no dirigido.
...por ejemplo si desde A se llega a B pero desde B no se llegare a A, entonces:

Código [Seleccionar] Expandir


A = B|F
B= C|F

Comparando con lo anterior se ve que ahora desde B no se puede acceder a A...

Igualmente estableciendo pesos, en la notación, podría ser expresado así:

Código [Seleccionar] Expandir


A = B:3|F:5
B= A:3|C:2|F:4
C= B:2|D:8|F:6
D= C:8|E:1|F:3
E= D:1|F:4 
F= A:5|B:4|C:6|D:3|E:4

De un nodoX a otro nodoY hay el mismo peso que del nodoY al nodoX.

...pero no tiene porqué ser el mismo peso de A a B que de B a A (aunque suele ser lo habitual, no es exigible que lo sea)... ejemplo:

Código [Seleccionar] Expandir


A = B:3|F:5
B= A:7|C:2|F:4
C= B:2|D:8|F:6
D= C:5|E:1|F:3
E= D:4|F:4 
F= A:7|B:3|C:5|D:3|E:4




Y ahora veré de responder a tus preguntas:

- 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.

Para este preciso propósito (conocer si un grafo es o no conexo) no.

A veces es preciso en un grafo señalar una forma en la que un nodo se atraviese a sí mismo un número determinado de veces, por ejemplo 2... en ese caso, es preferible añadir un nodo nuevo conectado igual que él, pero nombrado de forma distinta (como si fuera un nodo más).
Dentro de esta casuística puede suceder que está segunda aparición deba tener ciertas restricciones o reglas.
Por ejemplo podría estar conectado siempre junto a sí mismo como hace el nodo C en: A-B-C-C'-D-E.
En ese (hipotético) caso, se rediseña:
--- Los que conecten a C siguen conectados a C como antes.
--- El nuevo nodo creado (que por facilidad de reconocimeinto he bautizado como C' ), se conecta al resto de nodos como lo hacia C.
--- Pero C se conecta solo a C'.
--- Y C' podría o no, conectarse también a C si hubiera necesidad de señalar pesos distintos en la forma C-C' de C'-C. Es habitual que si un nodo es 'clonado' se otro (y siempre le precede-postcede), asuma un peso de 0.
Un ejemplo asumiendo en ese grafo tuyo que he tomado de ejemplo este caso, quedaría así (ahora sí, a la copia del nodo C' le ha acuñado un nombre específico Z):

A = B|F   
B= A|C|F 
C= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5. Este se desmontan en las dos siguientes reglas-nodos:
C= Z  //El nodo 2 se conecta así mismo, siempre, antes de conectarse a otros. Los otros conectan a C, y solo este a Z.
Z= B|D|F  // el nodo 2 está conectado a los nodos 2,4 y 5.
D= C|E|F 
E= D|F 
F= A|B|C|D|E 

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).

Esto te lo he respondido más arriba, pero resumo con un simple ejemplo:

Código [Seleccionar] Expandir


A= B|C|D
B= A|C
C=
D= B|C

En este ejemplo, puede verse como A conecta a B,C y D, pero solo B conecta a A. B y D conectan a C, pero C no conecta a ninguno. Puede verse fácilmente que no hay 'reciprocidad' en la conexión, no es exigible, pero es algo que dependerá siempre del contexto dle problema.
Por ejemplo en español tenemos: 'artículo->nombre', pero no: 'nombre->artículo'  (artículo<->nombre), así decimos: "El perro", y nunca: "Perro el", pero en cambio 'nombre->adjetivo' si admite 'adjetivo->nombre', como en: "El perro rabioso", "El rabioso perro".

- El peso de la conexión únicamente es útil para saber si dos nodos están conectados...

No. De hecho ni siquiera en tu ejemplo debiera basarse en ello. En tu ejemplo la conexión viene establecida por la matriz de adyacencia.
Perfectamente podría haber una conexión con peso 0.
El peso en realidad es (debe verse como) un valor abstracto, pero que por ejemplificar se tipifica con el significado de su nombre: peso, distancia, costo... es más fácil basar ejemplos en un valor que además de medible, es fácilmente identificable como la distancia entre dos nodos, para una mejor asimilación en su comprensión.

Sirven también para dirigir búsquedas, ya que puede haber reglas que imponen:
1 - buscar las rutas cuya suma en costo no superen x valor.
2 - buscar todas las rutas cuyo costo total sea exactamente x valor.
3 - buscar la/s ruta/s cuyo costo sea la menor (el plurar es porque a priori no puede descartarse que haya más de una ruta que siendo de costo menor sea igual a otra ruta distinta con igual costo).
4 - buscar todas las ruta que ... que se encuentre un nodo final. Aquí el costo no es un limitante solo un valor de resultado.
5 - buscar todas als rutas de x cantidad de nodos.
Incluso es normal (lo habitual) que las reglas de búsqueda reúnan más de 1 condición.

- ¿Alguna idea para corregir el bucle de la línea 96 y que no empiece desde cero?

Ya comentaba al principio, que lo ideal es una función de preprocesado que valide el grafo completamente.
Esa validación suele exigir 2 bucles (incluso 3 si el número de líneas no coincide con el número de nodos, loque es conveniente, para no tener un formato muy estricto, es habitual añadir líneas en blanco por claridad en la edición).
Si hay 3 bucles, el primero filtra las líneas que no parecen describir los nodos y los cuenta.
Luego se crea el array (vacío) de la cantidad de nodos que parecen existir.
A continuación un bucle donde verifican los nodos raíz (la parte izquierda, que otorga el nombre del nodo) y contabiliza (y guarda) cuantos hijos tiene cada nodo (examinando la parte derecha de la linea de texto).
Si no tiene hijos se queda en 0 (o si conviene con num_hijos= -1). Como hay referencias sin resolver (como sucede con los compiladores), esto es, se nombra un hijo que todavía no ha sido añadido en el array, es preciso un segundo bucle, donde ahora ya se trata de referenciar cada nodo hijo (para cada nodo del grafo) con el indice que ocupa en el array.
Ahora ya tu bucle ahí no sería:

Código [Seleccionar] Expandir

for (j = 0; j < num_nodos; j++)[/node]
Sino:
[code]
for (j = 1; j < nodo.num_hijos; j++)
Así salta por encima de los nodos que no tengan hijos (nodos terminales).
En ese punto, también hay algo que decir, a veces la condición de búsqueda exige el caso 4 de la pregunta previa... es decir un nodo sin hijos (num_hijos = 0) se considera un nodo terminal.
En realidad deben satisfacerse varios algoritmos de recorrdo cada uno basado en un criterio de búsqueda generalmente mixto, es decir hay varios condicionantes, no uno solo.

¿Se mejoraría la eficiencia del programa usando una pila en lugar del arreglo y la posición?

El array contiene los datos de entrada, la pila debe contener los nodos activos en el recorrido presente. Son cosas distintas.

Código [Seleccionar] Expandir


estructura DatosHijo
   entero index
   entero costo
fin estructura

funcion procesa_grafo(nodo n, ...)
    DatosHijo hijo
    entero index

    por cada hijo en n
        index = hijo.index  //se trata de una estructura, index refiere a la posición de dicho nodo en el array.

        Si pila.Contiene(index) = false
            pila.push(index) // <--------------------
            ...
            Si cumple condiciones de búsqueda
                ...
                imprimir pila.tostring
            si no
                ...
                procesa_grafo(arrayNodos(hijo), ...)
            fin si
            pila.pop(index) //<------------------
        fin si
    siguiente
    ...
fin funcion

buleano = funcion Contiene(entero index)
   devolver arrayNodos(index).Apilado
fin si

funcion Push(entero index)
    arraynodos(index).Apilado = true
   
    pila(cima) = index
    cima +=1
fin funcion

funcion Pop(entero index)
   arraynodos(index).Apilado = FALSE
   cima -=1
fin funcion

string= funcion ToString
    entero j, k, n
    string s

    bucle para k desde 0 a cima-1
        n += arrayNodos(pila(k)).nombre.length
    siguiente

    s = espacios(n)
    n= 0
    bucle para k desde 0 a cima-1
        j = arrayNodos(pila(k)).nombre.length
        s.insert(n, j, arrayNodos(pila(k)).nombre)
        n += j
    siguiente

    devolver s
fin funcion


Y lo principal: ¿existiría otro tipo de algoritmo que no fuera recorrer todos los caminos posibles?

Depende del contexto.
- Un grafo puede ser resumido a menudo para procesar menos nodos de los debidos si se dan determinadas condiciones
- También puede ser acortado si se exigen ciertas condiciones-reglas de búsqueda.

En el ejemplo que te daba en el enlace de más arriba, pese a que tiene 100 nodos, se recorren:

Número de nodos: 101
Total de caminos: 408694
Total de Salidas: 405294

El número de 'caminos' son los nodos visitados, las 'salidas' son las búsquedas halladas, como se ve, el número de nodos visitados 'extras' es muy reducido y se explica allí a que se debe.

Un ejemplo de resumen:
En el siguiente hilo,
https://foro.elhacker.net/programacion_cc/proyecto_de_estructura_de_datos_grafos_c-t484196.0.html;msg2163932#msg2163932
el grafo que dibuja el interesado (ver el primer mensaje), para los nodos B,D y H, se crea un nuevo nodo (no presente pero que los representa), nodo E. Éste hace las veces de los 3, porque los 3 están en línea, es decir

Código [Seleccionar] Expandir


C= A|B|L
B= D
D= H
H= F
F= A|C|H
Cada uno de esos nodos tiene como entrada el previo y como salida el siguiente, sin más conexiones, luego pueden resumirse como uno solo a efectos de recorrido, el nombre para el nodo E (para su impresión), podría asumir el valor concatenado de ellos, si bien como la dirección puede variar (BDH, o HDB), es preferible representarlo como 'E', y ya en la impresión saber que se leen en uno u otro sentido según el nodo previo (C ó F).
Ese grafo está condicionado solo por la búsqueda de un nodo terminal. Te vendría bien como ejercicio.

Un ejemplo de acortamiento por recorrido:

Código [Seleccionar] Expandir


    ...
    Si pila.Contiene(index) = false
        costoTotal += hijo.costo
        Si (costoTotal < CostoMaximo)
            pila.push(index)
            ... // entre otras cosas el recorrido recursivo
            pila.pop(index)
        fin si
    fin si
    ....

Como se ve en el ejemplo, si hay una condición de búsqueda, y con la suma del nodo se supera el costo máximo admitido, es claro que añadir al recorrido los hijos que este nodo tenga, no hará si no crecer el costo (asumiendo que no hay costos negativos, que no suele ser frecuente), luego todos los hijos que deriven de éste pueden ser omitidos...
En el siguiente enlace:
https://foro.elhacker.net/programacion_general/problema_del_viajante_de_comercio_branch_and_bound-t510012.0.html
...se puede ver comentado casos de este tipo, si bien interesaba al principio hacer un recorrido total (fuerza bruta ciega), solo por conocer los tiempos de cálculo.
Más al final (averiguado ya el tiempo y la exactitud de la solución) se abordó soluciones tirando justamente de esas reglas de recorrido, que además se actualizaba con cada hallazgo que mejoraba el previo (es decir el costo, al incio toma el valor de infinito, en realidad el valor máximo qe admite el tipo de datos numérico usado, que se va sustituyendo por cada costo menos que el previo):

Código [Seleccionar] Expandir


...
costoTotal += .costo
Si (costoTotal < CostoMaximo)
    costoMaximo = costoTotal
    pila.Tostring
sino
    pila.push(index)
    ... // entre otras cosas el recorrido recursivo
    pila.pop(index)
fin si
...

... para reducir la cantidad de nodos visitados al máximo... Incluso reordenando a la entrada (en el preprocesado), los hijos de cada nodo por su costo.

Ahora bien, para el caso de conocer si el grafo es conexo, no queda margen, pués la respuesta solicitada es sí/no.
No obstante salvo como ejercicio o que sean datos que te pasan... en resumen si los datos los provees tú mismo, ya sabes de entrada si el grafo es conexo, al momento de ir generando el grafo, luego puede ser superfluo.

Por último: ¿alguna manera de programar más elegante (o eficaz) sin usar una función recursiva. Tengo entendido que ... la recursividad no son muy bienvenidas por los programadores

Solo desde la ignorancia puede hacerse tal afirmación.

La iteración debe usarse donde es precisa, en vez de la recursión y la recursión debe usarse donde es precisa en vez de la iteración. Forzar el uso de un tipo de bucle cuando debe usarse el otro es cuando resulta ineficiente.

Éste es el caso propicio donde la recursión tiene cabida: grafos (un árbol no deja de ser un grafo).
Sabido es que la recursividad puede ser reconvertida en iteratividad, si bien en este caso, supone que entonces tu mismo debes acometer todo el trabajo de salvaguarda de datos en cada iteración que en su caso es cedido a los mecanismos de recursión que tiran de la pila del programa. Luego al final, solo añades código que enturbia o complica el algoritmo subyacente y no queda claro que vayas a ganar eficiencia toda vez que los mecanismo de recursión están muy optimizados.[/code]

[fzp]

Serapis: gracias por la respuesta, completísima y exhaustiva; te ha debido de llevar un buen rato redactarla. Muchísima información; me tomará tiempo digerirla, e indagar. Lo dicho: gracias por tus conocimientos y dedicación.

[Serapis]

... te ha debido de llevar un buen rato redactarla.

Sí... con las prisas (pues se avecinaba un texto largo), no lo revisé. He aprovechado ahora con más calma, para corregir sobretodo la ortografía (mi teclado suele comerse algunas letras, tengo que limpiarlo), y algún detalle menor o mejor redacción para que quede más claro, etc...


p.d.:

Olvidaba decirte, que en realidad si se puede hacerse el cálculo más abreviado para saber si el grafo es conexo o no, pero sólo en el caso de que sí lo sea, si no lo es, exigirá todo el recorrido igualmente.

Para ello, basta señalar como regla que cuando si pila alcance el número de nodos del grafo, entonces se demuestra que es conexo y puede salir y evitar el resto del recorrido (solo los numnodos de retornos).

Observa la diferencia en este recorrido:

Código [Seleccionar] Expandir


    nodo nodos []
    entero Pila[]
    entero cima, numnodos
    buleano nodirigido, Validado

    buleano = Inicializar(string grafo, string path)
        ...  // intenta establecer y validar el array nodos y crea la pila del tamaño numnodos
        validado = ....
        ...
        devolver validado
    fin funcion

    entero = funcion GrafoEsConexo(nodo n, entero numnodos, ...)
       buleano esconexo = FALSE

       si (validado = true)
            cima = 0
            si (nodirigido=TRUE)
                PilaPush(0)
                esconexo = RecorridoEsConexo(nodos[0] )
            sino  // si el grafo es dirigido, fuerza un recorrido desde cada nodo, para asegurarse.
                por cada nodo en nodos[]
                    PilaPush(k)
                    esconexo = RecorridoEsConexo(nodo)
                    PilaPop(k)
                    si (esconexo  = TRUE) salir del bucle                       
                    k +=1
                siguiente
            fin si
            PilaClear() // vaciar la pila.

            si (esconexo = TRUE)
                devolver 1     // es conexo
            sino
                devolver 0    // no es conexo
            fin si 
       sino
           devolver -1    // no se ha inicializado/validado el grafo.
       fin si
    fin funcion

// no necesitamos tirar del costo para calcular esto. La adyacencia los relaciona entre sí, por ese simple hecho.
buleano= funcion RecorridoEsConexo(nodo n)
    entero hijo  // indice absoluto en el array nodos[]
    buleano fin

    for cada hijo en n             
        si (PilaContiene(hijo) = false)
            PilaPush(hijo)                 
            fin = (cima< numnodos)             
            si (fin= FALSE)
                fin = RecorridoEsConexo(nodos[hijo] )
            fin si
            PilaPop(hijo)

            si (fin= TRUE)
                devolver TRUE  // sale de la función, es conexo
            fin si                 
        fin si
    siguiente

    devolver FALSE
fin funcion

El único modo de que la pila alcance el número de numnodos que tiene el grafo, es precisamente que sea conexo. Luego, tan pronto se alcance esa cantidad el recorrido puede finalizar. Si no es conexo, exigirá un recorrerlo completo.

La pila puese ser un objeto o un simple array y tener ahí mismo los métodos para su manejo, eso al gusto según acomode y el lenguaje elegido permite o facilita.

[fzp]

...
Olvidaba decirte, que en realidad si se puede hacerse el cálculo más abreviado para saber si el grafo es conexo o no, pero sólo en el caso de que sí lo sea, si no lo es, exigirá todo el recorrido igualmente...

...Para ello, basta señalar como regla que cuando si pila alcance el número de nodos del grafo, entonces se demuestra que es conexo y puede salir y evitar el resto del recorrido ...(solo los numnodos de retornos)...

Efectivamente, tienes toda la razón; no me había dado cuenta de ésto. Se puede terminar -en determinados caso que son los que dices- el algoritmo.

Por demás, decir que ya sé que no he entrado a fondo en los grafos. Sé que para para lo que realmente se usan hay que tener en cuenta las consideraciones que haces.

Lo de que hay que meter (en mi mini-programa) toda la matriz tampoco es así. Si ves el código, al crear la matriz de adyacencia (ahora sí lo he escrito bien   ) se inicializa a pesos = 0; o sea, por defecto todos los nodos están desconectados entre sí, y sólo hay que meter los que sí están conectados (dando un peso != 0). Siempre que el grafo pueda ser representado en un plano, no hay saltos tridimensionales (fuera del plano) de un nodo a otro, que son los grafos que me interesan; o sea que un nodo solamente estará conectado a un nº pequeño de otros nodos  (respecto del total de nodos), con lo cual solo hay que meter un pequeño número de conexiones de un nodo con otros.

Lo que no quita que, efectívamente, para aplicaciones prácticas de grafos (utilidades reales en la práctica), lo que comentas de buscar un método efectivo de almacenamiento en disco -por ejemplo en forma de texto- sean lo deseable. Ficheros que, una vez transformados a formatos entendibles por el programa, puedan ser tratados por éste.

Por ejemplo, me parece (sólo me parece) que el formato de los procesos padre|hijo, etc, me da la impresión de que podría ser parecido al concepto de "lista de adyacencia" (en lugar de la matriz). Aunque es sólo la impresión. La verdad, me cuesta un poco entender el concepto padre/hijo. Medio lo puedo entender en bifurcaciones en rama (árbol), pero en mallas (ejemplo simple: triángulos conectados en un plano) me cuesta más entender el concepto de padre/hijo. Y aún comprendiéndolo en bifurcaciones tipo rama de árbol, no consigo -aún, espero que algún día sí- comprender cómo se configuran dentro de un lenguaje.

No he profundizado más porque tampoco los grafos eran mi interés primordial. De hecho sólo me ha interesado la parte de "recorrer el grafo", porque me ha parecido que los grafos son una forma de aproximación (creo pero solo intuitívamente) que algo tienen que ver con los recorridos de laberintos (recorrer laberintos al azar y/o crear laberintos geométricos aleatóriamente). Por éso sólo me ha interesado la conexión entre nodos (SI/NO representada por un peso == 0 | != 0), y no el significado de esos pesos y la forma de maximizarlos/minimizarlos (por recorridos). Y por éso la forma que se me ocurrió de abordar el problema era la matriz, antes que la topología del grafo.

De todas formas, ha sido super-instructiva tu colaboración, una vez más, gracias.