Algoritmos de grafos
FACULDADE DE FILOSOFIA, CIÊNCIAS E LETRAS
TRABALHO DE GRAFOS
SANTO ANDRÉ
2013
SUMÁRIO
1- Introdução.................................................................................................. . 3
2- Algoritmo de Prim........................................................................................5
3- Algoritmo de Kruskal..................................................................................7
4- Algoritmo de Dijkstra.................................................................................15
5- Algoritmo de Boruvka.................................................................................21
6- Algoritmo de Bullman –Ford........................................................................25
7- Algoritmo de Ford-Fulkerson.......................................................................26
8- Conclusão.....................................................................................................28
9 – Bibliografia.................................................................................................29
Introdução
Para a resolução de alguns problemas em computação, algumas vezes é necessário calcular uma árvore. Esta árvore é tal que a soma das arestas que a constituem é a mínima possível. Pode haver mais do que uma arvore mínima de suporte, isto nos casos em que existem duas ou mais arvores no grafo em que a soma das arestas é a mesma. Existe, por fim, algoritmos que calculam esta árvore de suporte mínima, e são alguns desses algoritmos que vamos verificar.
Algoritmo de Prim
A ideia do Algoritmo de Prim é a de adicionar á árvore já existente o nó que está mais perto da mesma, á medida que ela se vai construindo. Quando todas as arestas estão na árvore, então a árvore de suporte mínimo fica concluída. Este algoritmo