Algoritmos de grafos

1431 palavras 6 páginas
CENTRO UNIVERSITÁRIO FUNDAÇÃO SANTO ANDRÉ
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

Relacionados

  • grafos algoritmo
    1003 palavras | 5 páginas
  • Algoritmos em grafos
    2963 palavras | 12 páginas
  • Algoritmo para Resolução de Grafos
    1560 palavras | 7 páginas
  • Comparativo entre algoritmos em grafos e programação matemática
    3121 palavras | 13 páginas
  • Algoritmo Para C Lculo De Centralidade Em Grafos
    6662 palavras | 27 páginas
  • Classe Grafo do algoritmo de prim
    507 palavras | 3 páginas
  • Estudo comparativo de algoritmos de busca com menor caminho em grafos
    2289 palavras | 10 páginas
  • Utilização de correspondência de grafos para reconhecimento de cenas através de algoritmos genéticos
    1067 palavras | 5 páginas
  • grafos- UFMG
    9612 palavras | 39 páginas
  • Teoria de grafos
    786 palavras | 4 páginas