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í...
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#msg2253267En 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í:
// 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:
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í:
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:
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:
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:
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.
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#msg2163932el 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= 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:
...
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):
...
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]
Autor
En línea
) 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.
