Título: Libreria de grafos Publicado por: m@o_614 en 24 Octubre 2013, 01:19 am Saludos
Tengo que hacer un programa que me dice que cree un grafos simple( no permite mas de una arista entre dos vertices), que sean dirigido o no dirigido y que puede agregar o eliminar aristas y vertices, pero la verdad no tengo muy claro si debo de hacerlo con un arreglo de listas que es una opcion que me dijo el profesor que podia hacer, pero yo la veo muy dificil porque nunca he hecho un arreglo de listas, y tampoco se si tengo que pedirle el numero de vertices y de aristas al inicio del programa, si tengo que verificar que no este vacio el grafo antes de eliminar un vertice,si los vertices los represento como nodos las aristas tambien las tengo que crear como nodos??,puedo crear una arista aun si no tengo vertices?? esto lo tengo que validar tambien?? les agredeceria que me dieran algunas sugerencias de como empezarlo porque no tengo ni la mas minima idea gracias Título: Re: Libreria de grafos Publicado por: rir3760 en 24 Octubre 2013, 03:19 am Una opcion para almacenar los vertices es una lista, la otra una matriz. Como siempre puedes empezar revisando sitios como Wikipedia (http://en.wikipedia.org/wiki/Graph_theory).
Un saludo Título: Re: Libreria de grafos Publicado por: m@o_614 en 24 Octubre 2013, 21:49 pm gracias rir3760 por tu respuesta, tu te refieres a almacenar los vertices con una lista ligada y las aristas con una matriz??? grafo[vertice1][vertice2] = arista, donde arista esta entre el vertice1 y el vertice2, pero si los vertices son nodos de una lista como los voy a poner como indice de una matriz??
Título: Re: Libreria de grafos Publicado por: rir3760 en 25 Octubre 2013, 16:22 pm En una matriz de adyacencias solo almacenas el peso del vértice o bien un valor especial para indicar que el vértice entre las aristas no existe. El caso de la lista de adyacencias es similar (solo si existe el vértice se almacena el peso correspondiente).
Si tenemos este grafo: Código: A ---- B ---- C ---- D La matriz de adyacencias es: Código: A B C D E F Un saludo Título: Re: Libreria de grafos Publicado por: m@o_614 en 30 Octubre 2013, 05:04 am Saludos, ya comence a hacer el codigo, primero tengo una typedef struct que me indica que voy a tener una matriz de tipo int a la que le tengo que asignar memoria dinamicamente y el numero de vertices, le pido cuantos vertices y aristas quiero, y despues inicializo el grafo, osea que cada uno de los elementos de la matriz sean -1 indicandome que no hay arista entre los vertices i y j, pero no se si esta parte y la de agregarArista estan bien hechas, exactamente esta parte:
Código
el codigo completo es este: Código
gracias |