elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el Twitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda con grafos en c
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con grafos en c  (Leído 5,644 veces)
marrison

Desconectado Desconectado

Mensajes: 179



Ver Perfil
Ayuda con grafos en c
« en: 17 Diciembre 2014, 18:46 pm »

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 Desconectado

Mensajes: 1.639


Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #1 en: 18 Diciembre 2014, 03:01 am »

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 Desconectado

Mensajes: 179



Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #2 en: 19 Diciembre 2014, 16:00 pm »

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

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Ayuda con grafos en c
« Respuesta #3 en: 21 Diciembre 2014, 03:53 am »

Debe ser algún algoritmo matemático conocido, pero implementado mediante colas, ¿no?

Bueno, estoy conjeturando ... :rolleyes:
En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
marrison

Desconectado Desconectado

Mensajes: 179



Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #4 en: 22 Diciembre 2014, 10:36 am »

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 Desconectado

Mensajes: 179



Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #5 en: 22 Diciembre 2014, 11:16 am »

Ahora mismo tengo esto para buscar los vecinos, pero no funciona..

Código
  1. void inicializarGrafo(struct grafo *grafo) {
  2. grafo->numNodos = 5;
  3. strcpy(grafo->nombres[0], "Centro");
  4. strcpy(grafo->nombres[1], "Ensanche");
  5. strcpy(grafo->nombres[2], "Fuenfresca");
  6. strcpy(grafo->nombres[3], "San Leon");
  7. strcpy(grafo->nombres[4], "San Julian");
  8.  
  9. grafo->matriz[0][0]=0;
  10. grafo->matriz[0][1]=1;
  11. grafo->matriz[0][2]=0;
  12. grafo->matriz[0][3]=1;
  13. grafo->matriz[0][4]=1;
  14. grafo->matriz[1][1]=0;
  15. grafo->matriz[1][0]=1;
  16. grafo->matriz[1][2]=1;
  17. grafo->matriz[1][3]=0;
  18. grafo->matriz[1][4]=1;
  19. grafo->matriz[2][2]=0;
  20. grafo->matriz[2][0]=0;
  21. grafo->matriz[2][1]=1;
  22. grafo->matriz[2][3]=1;
  23. grafo->matriz[2][4]=1;
  24. grafo->matriz[3][3]=0;
  25. grafo->matriz[3][0]=1;
  26. grafo->matriz[3][1]=0;
  27. grafo->matriz[3][2]=1;
  28. grafo->matriz[3][4]=1;
  29. grafo->matriz[4][0]=1;
  30. grafo->matriz[4][1]=1;
  31. grafo->matriz[4][2]=1;
  32. grafo->matriz[4][3]=1;
  33. grafo->matriz[4][4]=0;
  34. }
  35.  
  36. void buscarVecinos(struct grafo *grafo, int indiceNodo, char Nodo) {
  37. int nodo_origen, i;
  38. char nodo_origenl, nodo;
  39. printf("Selecciona un nodo: \n 0.-Centro\n1.-Ensanche\n2.-Fuenfresca\n3.-San Leon\nSan Julian\n");
  40. scanf("%d", &nodo_origen);
  41. for (i=0;i==4;i++) {
  42. if (grafo->matriz[nodo_origen][i]==1) {
  43. nodo = *grafo->nombres[i];
  44. nodo_origenl = *grafo->nombres[nodo_origen];
  45. printf("%d es vecino de %d",nodo_origenl, nodo);
  46. }
  47. }
  48. }

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

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Ayuda con grafos en c
« Respuesta #6 en: 22 Diciembre 2014, 14:16 pm »

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 Desconectado

Mensajes: 179



Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #7 en: 23 Diciembre 2014, 10:50 am »

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 Desconectado

Mensajes: 179



Ver Perfil
Re: Ayuda con grafos en c
« Respuesta #8 en: 29 Diciembre 2014, 12:55 pm »

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

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: Ayuda con grafos en c
« Respuesta #9 en: 2 Enero 2015, 14:29 pm »

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.)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Grafos
Java
soser 1 3,220 Último mensaje 4 Noviembre 2010, 22:53 pm
por Debci
Ayuda con mi proyecto de grafos « 1 2 »
Programación C/C++
JorgeKun 18 13,418 Último mensaje 12 Junio 2011, 18:38 pm
por JorgeKun
ayuda urgente laberinto con grafos
Programación C/C++
blaaaack 0 3,966 Último mensaje 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,572 Último mensaje 10 Noviembre 2018, 17:17 pm
por Beginner Web
Ayuda Con Este ERROR, GRAFOS
Programación General
verakra 1 2,661 Último mensaje 29 Febrero 2020, 21:55 pm
por K-YreX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines