Título: Grafos Publicado por: Beginner Web 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
Título: Re: Grafos Publicado por: AlbertoBSD en 7 Noviembre 2018, 02:13 am Tiene que ser necesariamente con lista enlazada?
Saludos Título: Re: Grafos Publicado por: Beginner Web 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
Título: Re: Grafos Publicado por: AlbertoBSD 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
Título: Re: Grafos Publicado por: MAFUS 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 Título: Re: Grafos Publicado por: AlbertoBSD 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
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! Título: Re: Grafos Publicado por: MAFUS en 7 Noviembre 2018, 19:26 pm Tienes razón. Voy con desgana. :-(
Título: Re: Grafos Publicado por: Beginner Web 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? ;-)
Título: Re: Grafos Publicado por: AlbertoBSD 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 |