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

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Grafos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Grafos  (Leído 2,466 veces)
Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Grafos
« en: 7 Noviembre 2018, 01:44 am »

No entiendo bien la definicion de estructura de grafos utilizando listas enlazadas, masomenos lo entiendo pero ahora me perdi, alguien sabe? gracias?

Código
  1. typedef struct arco *parco;
  2. typedef struct vertice *pvertice;
  3. typedef struct arco{
  4. float peso;
  5. pvertice destino;
  6. parco sigarco;
  7. };
  8. typedef struct vertice{
  9. int id;
  10. pvertice sigvertice;
  11. parco lista_arco;
  12. };


En línea

7w7
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Grafos
« Respuesta #1 en: 7 Noviembre 2018, 02:13 am »

Tiene que ser necesariamente con lista enlazada?

Saludos


En línea

Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Grafos
« Respuesta #2 en: 7 Noviembre 2018, 04:17 am »

Si, con "listas enlazadas", estas estructuras van creciendo a medida que se registran mas llamadas de un telefono a otro me parece, es decir es una estructura de M:N
En línea

7w7
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Grafos
« Respuesta #3 en: 7 Noviembre 2018, 16:50 pm »

Realmente es una forma muy conveniente de tener una lista de todos los nodos de forma accesible

Imaginemos el siguiente problema

Digamos que te dejan crear un Grafo con un 10 Millones de Nodos, imagina tu que haces todo perfectamente, los enlaces entre nodos, los pesos de las aristas etc...

En ese mismo problema te indican que  tienes que hacer limpieza de X cantidad de Nodos ya sea algunos cuantos o todos.
Supongamos que es el mejor de los casos y que te piden borrar el grafo, para crear uno nuevo.

Lo mas facil seria crear un nuevo grafo y olvidarnos del anterior verdad?

pero son 10 Millones de nodos que siguen en la memoria  :rolleyes: :rolleyes:

Lo logico es borrar todos los nodos y liberar la memoria que se utilizo en el momento.

¿Como lo harias sin tener una lista de todos los nodos?

En caso de no tener una lista con todos los nodos, lo mas seguro es que tengas que recorrer el grafo nodo por nodo creando una lista de los nodos que ya liberastes y los que te faltan por liberar, lo cual podria llegar a ser un poco ineficiente.

Entonces mejor tener una lista que puedas recorrer de forma facil y sencilla para ir eliminándolos de uno por uno.


Veamos el siguiente codigo con una aproximaacion a generar un grado de forma muy sencilla.

Siendo el "Grafo" realmente un simple apuntador a un nodo, y cada nodo puede apuntar a mas nodos.

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. typedef struct str_nodo *Nodo;
  5.  
  6. typedef struct str_nodo {
  7. int valor;
  8. Nodo *nodos; //Nodos con los que esta unido el nodo actual
  9. int n_nodos;
  10. }*Grafo;
  11.  
  12. Nodo crear_nodo(int valor);
  13. void agregar_nodo(Nodo inicial,Nodo final); //Esta funcion une ambos nodos
  14.  
  15. int main() {
  16. Grafo grafo;
  17. grafo  = crear_nodo(10);
  18. agregar_nodo(grafo,crear_nodo(5)); //Aqui tenemos el nodo 10 <-> 5 Que apunta al nodo 5
  19. agregar_nodo(grafo,crear_nodo(15));
  20. agregar_nodo(grafo,crear_nodo(800));
  21. agregar_nodo(grafo,crear_nodo(100));
  22. //En este punto parece sencillo recorrer todos los nodos existentens, pero las cosas se podrian complicar un poco si agregamos nodos a los nodos ya existententes de forma aleatoria
  23. return 0;
  24. }
  25.  
  26. Nodo crear_nodo(int valor) {
  27. Nodo nodo;
  28. nodo = calloc(1,sizeof(struct str_nodo));
  29. nodo->valor = valor;
  30. nodo->nodos = NULL;
  31. nodo->n_nodos = 0;
  32. return nodo;
  33. }
  34.  
  35. void agregar_nodo(Nodo inicial,Nodo final) {
  36. inicial->nodos = realloc(inicial->nodos,(inicial->n_nodos +1 )*sizeof(struct str_nodo*)); //Incrementamos el espacio para (inicial->n_nodos +1) Apuntadores
  37. final->nodos = realloc(final->nodos,(final->n_nodos +1 )*sizeof(struct str_nodo*)); //Incrementamos el espacio para (final->n_nodos +1) Apuntadores
  38.  
  39. inicial->nodos[inicial->n_nodos] = final;
  40. final->nodos[final->n_nodos] = inicial;
  41.  
  42. printf("%i <-> %i\n",inicial->valor,final->valor);
  43. inicial->n_nodos++;
  44. final->n_nodos++;
  45. }
En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Grafos
« Respuesta #4 en: 7 Noviembre 2018, 17:07 pm »

Una imagen vale mas que mil palabras:
Es en Java, pero la explicación es válida para cualquier lenguaje.
https://www.youtube.com/watch?v=X5hR5iLWBeU
« Última modificación: 7 Noviembre 2018, 17:08 pm por MAFUS » En línea

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Grafos
« Respuesta #5 en: 7 Noviembre 2018, 17:12 pm »

Una imagen vale mas que mil palabras:
https://www.youtube.com/watch?v=X5hR5iLWBeU

Que pasa MAFUS.

Yo crei que si el usuario estaba preguntando por grafos, ya conocía el concepto de listas enlazadas.

Volviendo a mi ejemplo hice la siguiente generacion de nodos creados aleatoriamente, y al final el programa llego a utilizar 53 MB de memoria.

Código
  1. int main() {
  2. int i,j;
  3. Grafo grafo,temp;
  4. srand(time(NULL));
  5. grafo  = crear_nodo(rand());
  6. i = 0;
  7. while(i < 1000000) {
  8. agregar_nodo(grafo,crear_nodo(rand()));
  9. i++;
  10. }
  11.  
  12. i = 0;
  13. while(i < 1000) {
  14. temp = grafo->nodos[rand() % grafo->n_nodos];
  15. j = 0;
  16. while(j < 200) {
  17. agregar_nodo(temp,crear_nodo(rand()));
  18. j++;
  19. }
  20. i++;
  21. }
  22. getc(stdin);// Solo para que no se cierre el programa pero no me gusta usar getc
  23. return 0;
  24. }
  25.  


Entonces si quisieramos elimintar todos los Nodos de forma Rapida para liberar la memoria,
¿Cual seria la forma mas facil de eliminarlos?

Respuesta:  ir guardando los nodos en una lista para posteriormente poder recorrerlos facilmente.

Saludos!
En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Grafos
« Respuesta #6 en: 7 Noviembre 2018, 19:26 pm »

Tienes razón. Voy con desgana.  :-(
En línea

Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Grafos
« Respuesta #7 en: 8 Noviembre 2018, 02:26 am »

La verdad tienen razon chicos, pero estas estructuras las iba a utilizar en cosas pequeñas tampoco quiero hacer mi propia red social o compania telefonica sin ofender, solo queria entender esta estructura. Es algo enredada no?  ;-)
En línea

7w7
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Grafos
« Respuesta #8 en: 8 Noviembre 2018, 04:56 am »

Los grafos como tal son bastante enredados, y mas si todavia tienes dudas de estructuras mas basicas como listas ligadas, doblemente ligadas, circulares, y demás.

Pero si entiendes los grafos avanzaras mucho en tu entendimiento del la programación en cualquier lenguaje.

básicamente se utiliza la lista ligada para mantener un control sobre el numero total de nodos creados, pero no indica que la estructura de Lista ligada necesariamente tenga que ser parte de grafo.

saludos
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Grafos
Java
soser 1 3,065 Último mensaje 4 Noviembre 2010, 22:53 pm
por Debci
grafos
Programación General
kailon 3 3,468 Último mensaje 6 Junio 2011, 16:54 pm
por Valkyr
Grafos C++
Programación C/C++
Rashed 1 1,675 Último mensaje 13 Mayo 2014, 08:57 am
por eferion
grafos
Java
carliches 0 1,387 Último mensaje 16 Mayo 2016, 20:28 pm
por carliches
Grafos
Programación C/C++
Beginner Web 1 1,268 Último mensaje 10 Enero 2019, 19:53 pm
por MAFUS
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines