Árvore geradora Mínima. Entrada: Um grafo

cicicae
(usa Ubuntu)

Enviado em 13/06/2008 - 17:30h

Ola gente.
não sei nada sobre grafos, preciso fazer u´m algoritmo em C que faça uma árvore geradora mínima - dado de entrada: um grafo.

Alguem tem algum aloritmo de grafo em C, pra eu tomar de exemplo???????
Ou alguem tem isso implementado???


Abraços Cintia

mestrekame
(usa Outra)

Enviado em 13/06/2008 - 20:17h

Não tenho o algoritmo pronto mas acho que posso lhe dar algumas dicas de como implementar,

primeiro vc aprende alguns conceitos básicos sobre grafos

http://pt.wikipedia.org/wiki/Teoria_dos_grafos
http://www.dpi.ufv.br/disciplinas/inf330/files/Grafo_cap0.doc


depois vc monta um grafo como uma estrutura de matriz de adjacencias

http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/adjmatrix.html

depois vc imprementa um algoritmo (o que vc ta precisando) que recebe esse grafo como entrata e aplica o algoritmo sobre ele

http://www.engprod.ufjf.br/fernando/epd015/arvore_geradora_minima.pdf

bons estudos :)

abraço