Autor
|
Tema: Ayuda con grafos en c (Leído 5,697 veces)
|
marrison
Desconectado
Mensajes: 179
|
Hola buenas, tengo que hacer un grafo para la universidad en c, y la verdad es que estoy bastante atascado..
He estado buscando pero no encuentro nada que me sirva.. alguien podria ayudarme?
Tengo que realizar un grafo, sin ponderar y sin dirigir, bien sencillito.
Para empezar he puesto 5 nodos, y he creado la matriz de adyacencia, hasta ahi bien.
El problema es que no se como hacer para buscar los vecinos y buscar el camino minimo, es decir, que te digan el origen y el destino y tu indiques el camino minimo... ahi estoy atascado...
Por lo que tengo entendido hay que crear una cola ciruclar, pero no se como, estoy bastante liado..
alguna ayuda?
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
rir3760
Desconectado
Mensajes: 1.639
|
Para encontrar la ruta mas corta entre dos vértices en un grafo no dirigido puedes utilizar el algoritmo de Dijkstra. Un saludo
|
|
|
En línea
|
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly. -- Kernighan & Ritchie, The C programming language
|
|
|
marrison
Desconectado
Mensajes: 179
|
No me dejan utilizarlo, me hacen hacerlo con una cola
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
Yoel Alejandro
|
Debe ser algún algoritmo matemático conocido, pero implementado mediante colas, ¿no? Bueno, estoy conjeturando ...
|
|
|
En línea
|
Saludos, Yoel. P.D..- Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
|
|
|
marrison
Desconectado
Mensajes: 179
|
La verdad es que no tengo ni idea, no nos ha dicho nada mas... para la vuelta de navidad traed un grafo que busque el camino mas corto entre los nodos mediante colas...
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
marrison
Desconectado
Mensajes: 179
|
Ahora mismo tengo esto para buscar los vecinos, pero no funciona.. void inicializarGrafo(struct grafo *grafo) { grafo->numNodos = 5; strcpy(grafo ->nombres [0], "Centro"); strcpy(grafo ->nombres [1], "Ensanche"); strcpy(grafo ->nombres [2], "Fuenfresca"); strcpy(grafo ->nombres [3], "San Leon"); strcpy(grafo ->nombres [4], "San Julian"); grafo->matriz[0][0]=0; grafo->matriz[0][1]=1; grafo->matriz[0][2]=0; grafo->matriz[0][3]=1; grafo->matriz[0][4]=1; grafo->matriz[1][1]=0; grafo->matriz[1][0]=1; grafo->matriz[1][2]=1; grafo->matriz[1][3]=0; grafo->matriz[1][4]=1; grafo->matriz[2][2]=0; grafo->matriz[2][0]=0; grafo->matriz[2][1]=1; grafo->matriz[2][3]=1; grafo->matriz[2][4]=1; grafo->matriz[3][3]=0; grafo->matriz[3][0]=1; grafo->matriz[3][1]=0; grafo->matriz[3][2]=1; grafo->matriz[3][4]=1; grafo->matriz[4][0]=1; grafo->matriz[4][1]=1; grafo->matriz[4][2]=1; grafo->matriz[4][3]=1; grafo->matriz[4][4]=0; } void buscarVecinos(struct grafo *grafo, int indiceNodo, char Nodo) { int nodo_origen, i; char nodo_origenl, nodo; printf("Selecciona un nodo: \n 0.-Centro\n1.-Ensanche\n2.-Fuenfresca\n3.-San Leon\nSan Julian\n"); scanf("%d", &nodo_origen ); for (i=0;i==4;i++) { if (grafo->matriz[nodo_origen][i]==1) { nodo = *grafo->nombres[i]; nodo_origenl = *grafo->nombres[nodo_origen]; printf("%d es vecino de %d",nodo_origenl , nodo ); } } }
He hecho una matriz de adyacencia que marca 1 si estan conectados y 0 si no lo estan, luego pido un nodo de origen, y hago un for para que recorra toda la matriz de adyacencia y si encuentra uno que sea 1 que lo escriba en pantalla, pero no funciona... Eso es para buscar los vecinos, no para el camino.. Alguna ayuda?
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
Yoel Alejandro
|
La idea debe ser buscar recursivamente, por ensayo y error, hasta encontrar el punto final de la ruta.
Te paras en el primer nodo, y luego entre todos los (n-1) nodos restantes hay algunos que se conectan con el primero (y otros que quizá no). Digamos que hay M1 nodos que se conectan con el primero, entonces debes explorar todas estas M1 posibilidades. Cada un de ellos a su vez genera nuevas posibilidades de conectarse con un tercer nodo y así sucesivamente.
Pero a mí esta idea se me va pareciendo más a un árbol de búsqueda de múltiples ramas, que a una cola ....
Es cuestión de hacer un algoritmo en papel, ejecutarlo "a mano", y luego pasarlo a código de programación. Al final, tendrás un cierto número de soluciones al problema (suponiendo que hay una al menos), y elegirás la trayectoria con menos nodos como la más corta.
Voy a ver si al final de este día te preparo algo mejor y te lo envío. Ten en cuenta también que quizá tenemos zonas horarias diferentes tú y yo.
|
|
|
En línea
|
Saludos, Yoel. P.D..- Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
|
|
|
marrison
Desconectado
Mensajes: 179
|
Y como comparo y guardo los nodos que estan conectados?
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
marrison
Desconectado
Mensajes: 179
|
He ido probando cosas pero nada... alguna ayuda?
Una duda, como se pasan los structs por referencia?
|
|
|
En línea
|
"Es genial trabajar con ordenadores. No discuten, lo recuerdan todo y no se beben tu cerveza" (Paul Leary)
"Controlar la complejidad es la esencia de la programación" (Brian Kernigan)
"Primero resuelve el problema. Entonces, escribe el código" (John Johnson)
"640K deberían ser suficientes para todo el mundo" (Bill Gates, 1981)
|
|
|
Yoel Alejandro
|
Hola Marrison, estuve leyendo sobre el tema del algortimo Dijkstra y me pareció muy interesante. Voy a publicar hoy un post sobre el tema y te invitaré a consultarlo.
|
|
|
En línea
|
Saludos, Yoel. P.D..- Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Grafos
Java
|
soser
|
1
|
3,237
|
4 Noviembre 2010, 22:53 pm
por Debci
|
|
|
Ayuda con mi proyecto de grafos
« 1 2 »
Programación C/C++
|
JorgeKun
|
18
|
13,546
|
12 Junio 2011, 18:38 pm
por JorgeKun
|
|
|
ayuda urgente laberinto con grafos
Programación C/C++
|
blaaaack
|
0
|
4,006
|
20 Junio 2017, 02:33 am
por blaaaack
|
|
|
ayuda con recorrido de grafos en amplitud y profundidad
Programación C/C++
|
Beginner Web
|
0
|
1,605
|
10 Noviembre 2018, 17:17 pm
por Beginner Web
|
|
|
Ayuda Con Este ERROR, GRAFOS
Programación General
|
verakra
|
1
|
2,699
|
29 Febrero 2020, 21:55 pm
por K-YreX
|
|