Título: Proyecto de Estructura de datos.... GRAFOS!!! :c Publicado por: axel19 en 27 Mayo 2018, 03:38 am Hola comunidad!!!
Publico esto para pedir su ayuda Necesito realizar un programa que me de las diferentes rutas posibles dentro de un grafo Entiendo que esto lo puedo realizar con una matriz de Adyacencia con 1 y 0 Como podría realizar este procedimiento??? L / C ---B----D |\ | | \ | A---F------H Por ejemplo en este grafo me las rutas para ir de A a L A->C->L , A->F->C->L , A->F->H->D->B->C->L Título: Re: Proyecto de Estructura de datos.... GRAFOS!!! :c Publicado por: anubisdark en 27 Mayo 2018, 16:55 pm Lo que puedes hacer es una clase Grafo, en los cuales tenga solo 3 nodos, si son grafos supuestamente vas a tener dos apuntadores el izquierdo y el derecho, si es un diagrama de Hasse, si no es ese caso, entonces vas a tener más nodos, después de crear ese insert, lo que haces es un backtracking, en el que le pasas un contador por referencia, y vas probando... Yo la verdad lo que haría es que en cada nodo guardo un contador que me diga cuantos saltos tengo que hacer de un nodo A a un nodo B, como sale en tu ejemplo, por ejemplo sería, que en el nodo F, guardo en una variable cuantos saltos tengo que hacer para llegar a L, y cual es su camino en un string.
Título: Re: Proyecto de Estructura de datos.... GRAFOS!!! :c Publicado por: Serapis en 27 Mayo 2018, 21:00 pm Antes que nada, debes decidir/indicar, si es admisible que se revisite un nodo dos ó x veces, ó solo una como máximo... sino, por ejemplo sería valido la ruta:
A->C, B, D, H, F, C, L ...Que, como se puede ver, revisita el nodo C dos veces... Una vez decidido, y dando por supuesto que no se admitite revisitar nodos, puede tratarse como un automata finito determinista (AFD), donde el alfabeto es el conjunto de nodos (A, B, C, D, F, H, L) donde el estado inicial es A y el estado final es L, entonces puede establecerse el resto de nodos como estados de transición entre uno y otro. Así desde A solo puede accederse a F y a C, lo que por ejemplo tratado como un autómata finito determinista , se señalaría en BNF como: A = C|F y desde C, se puede acceder a los nodos C = A|F|B|L El resto d eproducciones: F = A|H H = F|D D = H|B B = C|D L = C <--- esta no interesa, se trata de llegar a L, no pasar po él (es el estado final, no un estadode transición) Como se puede ver, las producciones BNF, son las adyacencias de un nodo, la cantidad de nodos a los que se accede (por ejemplo A|F|B|L) son las aristas que salen de dicho nodo (en el ejemplo del nodo C, en C = A|F|B|L). Entonces una vez en el estado inicial (A, pongamos estado 1), solo puede transitar hacia un estado 2, y desde un estado 2 a otro estado 2 o al estado de transición 3, si no tiene otro nodo que sea visitable que uno ya visitado, va al estado de error y por tanto ese camino no tiene solución, debe volverse un paso atrás cada vez que esto suceda... el estado de transición 3 (L), es el estado final, y señal de que admite ese 'token', para la gramática del alfabeto propuesto... Puede tratarse como un automata de pila, porque un nodo no puede visitarse más de una vez... A diferencia claro, de por ejemplo cuando se hace un compilador que en la entrada viene un texto y se trata de ver si un token pertenerce o no a la gramática, en tu caso haces algo distinto, la entrada es nula y tratas de averguar todas las salidas válidas (para una gramática libre de contexto serían incontables), pero para el caso de un grafo como el del ejemplo, es finito... ...de entrada se sabe que como máximo la longitud de palabra es la del alfabeto (ó menor)... Por cuestiones de rendimiento, la pila realmente puede ser remplazada por un array de bytes donde cada letra del alfabeto tenga un valor true (no visitado ún, esto es, es Visitable), y una vez usado (pop si fuera una pila) su valor se ponga a false (nodo visitado, no visitable ya)... la velocidad de usar el array sobre una pila, está en el acceso aleatorio. al no exigir tener que extraer lo de encima de la pila... para acceder a un nodo. Aquí un pseudocódigo casi completo... la función donde ba todo el trabajo lo dejo a tu esfuerzo... Código: funcion TodasLasRutasDeUnGrafo(string alfabeto) // sin repetir nodo. Código: // el array es fijo según el grafo, y tal como se indico en las producciones. Código: array de bytes = funcion LlenarPila(string alfabeto) Y la función final que lleva todo el trabajo, la dejo a tu esfuerzo... pero con algunas anotaciones. Código: enumeracion Estados Finalmente decirte que casi siempre verás una solución con un cuerpo más matemático, tirando de árboles... , la solución (incompleta) que te aporto, es... no más cercana, sino íntima a la programación... pués entra en la parte de la teoría de compiladores. Aunque al caso ha habido una discreta variación... a medias entre un análisis léxico y sintáctico. Otra solución es recurrir a la combinatoria... generar (ir generando y probando sobre la marcha cada una si es un camino, esto es si el siguiente nodo es accesible desde el actual) todas las permutaciones sin repetición de largo máximo el alfabeto Como algoritmo es mucho más simple, pero es más lento en ejecución, especialmente si el alfabeto fuera mucho más largo, para este cortito, todavía no es significativo. Código: string permutacion, ruta Título: Re: Proyecto de Estructura de datos.... GRAFOS!!! :c Publicado por: Serapis en 29 Mayo 2018, 20:17 pm mmmm... es típico que alguien venga preguntando algo, y luego nunca comparezca, ni siquiera para ver si han respondido...
Si lo que sucede es que te asusta la respuesta, te aclaro que se puede simplificar, pero (resulta conveniente) que antes haya algún "feedback", que demuestre que tienes interés en aprender y no solo en tener una tarea lista. De todos modos, como va a resultar en incomparecencia, no dejaré a otros en la intriga. Del mismo modo, que por ejemplo, cuando intentamos trazar un área dados unos segmentos (medida y ángulo), que delimitan el perímetro... que si sucede, como en el siguiente ejemplo que: A-------B-------------C----D AB mide 8, angulo = g BC mide 13, angulo = g CD mide 4, angulo = g Teniendo todos ellos el mismo ángulo y yendo uno a continuación del otro, se puede simplificar los 3 como un único segmento del mismo ángulo pero de longitud la suma de todos ellos: A-------------------------D AD mide AB + BC + CD = 25, angulo = g No necsitamos nada más de dicho ejemplo... (un ejemplo sencillo de entender por todo el mundo). Del mismo modo cuando hay grafos que son antecedidos por solo un nodo y seguido de también un solo nodo, un tramo así igualmente puede ser resumido en uno equivalente... en tu caso, entonces: F-H-D-B-C, puede ser resumido como uno nuevo E = HDB que los remplace. Y por tanto considerar, solo las producciones A = C|F y desde C, se puede acceder a los nodos C = A|F|E|L F = A|C|E E = C|F <---- el nuevo nodo que remplaza (para simplificar) a los 3 intermedios. Si lo montas en un árbol sintáctico (que corresponde al algoritmo, señalado más arriba)... se obtiene esto... debajo lo explico por encima, aunque es autoexplicativo, si lo observas el suficiente tiempo... (https://i.imgur.com/v1yfMNe.png) La raíz es la producción general, la solución. Debajo se ponen como hijos cada uno de las alternativas que salen desde "A" (el nodo padre). De igual modo debajo de cada nodo, se pone las alternativas de esa producción. De esa manera se va completando el árbol... Los nodos pintados de verde, son los rechazados. y se rechazan, porque ya han sido visitados... toma un nodo verde, revisa sus ancentros, y verás que ya consta en esa ruta. Una vez que un nodo es tachado, ya no cabe más descencia de él. Finalmente (en alguno) se llega al estado terminal, "L"... Todas las rutas de la raíz "A" a cada una de los nodos terminales "L", son las soluciones que buscas (las he marcado con nodos rojos y caminos en amarillo). Finalmente se ponen todas, juntas debajo y habiendo recordado deshacer "E", que lo hemos tenido simplificado durante el proceso. |