Título: Un algoritmo para calcular si un grafo es conexo o no Publicado por: fzp en 12 Diciembre 2021, 15:15 pm 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
Algunos ejemplo que he hecho (https://i.imgur.com/LdE39Zp.jpeg) (https://i.imgur.com/hlUTiS3.jpeg) 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. Título: Re: Un algoritmo para calcular si un grafo es conexo o no Publicado por: Serapis en 12 Diciembre 2021, 22:53 pm 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: buleano Validado - 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: // nota: al poner 'conectado a' debe entenderse 'directamente conectado a' 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: A = B|F Igualmente estableciendo pesos, en la notación, podría ser expresado así: Código: A = B:3|F:5 ...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: A = B:3|F:5 Y ahora veré de responder a tus preguntas: Citar - 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): Citar A = B|F B= A|C|F 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 Citar 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: A= B|C|D 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". Citar - 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. Citar - ¿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: for (j = 0; j < num_nodos; j++)[/node] 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. Citar ¿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: estructura DatosHijo Citar 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: Citar 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: C= A|B|L 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: ... 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: ... 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. Citar 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] Título: Re: Un algoritmo para calcular si un grafo es conexo o no Publicado por: fzp en 13 Diciembre 2021, 11:32 am 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.
Título: Re: Un algoritmo para calcular si un grafo es conexo o no Publicado por: Serapis en 13 Diciembre 2021, 18:09 pm ... 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: nodo nodos [] 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. Título: Re: Un algoritmo para calcular si un grafo es conexo o no Publicado por: fzp en 30 Diciembre 2021, 18:31 pm ... 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 :D ) 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. Título: Re: Un algoritmo para calcular si un grafo es conexo o no Publicado por: Serapis en 31 Diciembre 2021, 18:16 pm 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. Para empezar (con los grafos), lo importante es siempre ser capaz de entenderlo y por tanto resolverlo... Las optimizaciones siempre vienen al final (cuando se verifica que funciona todo correctamente), especialmente cuando urge que así sea porque el espacio de soluciones es inmenso y el tiempo excesivo o más bien intolerable o intratable... para casos en que una respuesta se obtenga en lo que dura parpadeo, no importa que sea subóptimo... 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. Frente a la de 'matriz de adyacencia', está lo que se llama 'lista de adyacencia'.A menudo (las listas de adyacencia) suelen operarse como listas enlazadas, pero cuando se busca el mayor rendimiento posible en tiempo, es preferible convertirlo en array (si el sistema se deja) a cambio de un escaso tiempo inicial de preprocesado. Si el sistema tiene una complejidad baja, suele bastar un simple string y/o si tiene una complejidad media vía un fichero de texto. Si el sistema es más complejo o es cambiante de forma dinámica, es preferible crear una clase, que permita dinámicamente añadir, eliminar y modificar los nodos, algo como: Código: nodo n = nuevo nodo Ambos modos son de interés, pero el uso de uno u otro suele venir abordado por el tipo de problema, es decir, según se requiera. Como modo general, puede establecerse que la matriz de adyacencia es el método adecuado cuando el número de conexiones entre los nodos es muy elevada. Por ejemplo en el problema (general) del viajante de comercio, todos los nodos están conectados a todos los nodos. La lista de adyacencia en cambio suele ser más conveniento cuando en el grafo cada nodo tiene pocas conexiones a otros nodos, respecto de la cantidad total de nodos presentes en el grafo. Por lo demás las conexiones, pueden verse así de simple como conexiones, o como referencias a padre/hijo, elegir un modelo de visionarlo, suele dejarse a la preferencia de la intuición, pués así acomoda mejor y queda menos abstracto, con lo que te resulta más cómodo tirar de una visión u otra... por ejemplo en sistemas binarios, muchos prefieren la alusión de derecha/izquirda, para la referencia a los nodos hijo... para mí incluso un nodo padre, es un hijo respecto del que se ve como su hijo, en función pués de la dirección del flujo del recorrido (naturalmente cuando un grafo es dirigido, cierta conexiones son unilaterales, luego (simplificando) toda conexión la veo como un hijo o ciega (ciega= inexistente, aunque a veces en sistemas más complejos, puede ser condicionado dicho caso por otros medios al margen de haber sido visitado))... hay quien prefiere tirar de 'anterior/siguiente'. Hay quien de la nomenclatura, quiere hacer un sistema rígido, cuando a todas luces debe ser flexible, pues existe para asistir al ser humano, no para imponerle 'reglas'. No temas patear la nomenclatura cuando lejos de ayudar, esclaviza. 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. En la vida real, lo normal es que te encuentres siempre con grafos. Otros tipos de estructuras en la vida real, no suelen darse, a menudo son simplificaciones de ellos o en todo caso maquinaciones conceptualmente humanas... recuerda aquel dicho romano: 'divide y vencerás'.Pero no importa si te acercas a los grafos por una u otra razón, es adecuado conocerlos, pero (al programar) como mínimo ser capaz de recorrerlos. En programación hay que aventurarse a los diferentes campos que ofrece sin miedo y no hay obligación de profundizar al máximo, a menudo es solo curiosidad o una necesidad puntual. |