Algoritmos de Grafos: Kruskal, Dijkstra e A*
Classificado em Tecnologia
Escrito em em
português com um tamanho de 2,9 KB
Algoritmo de Kruskal: O algoritmo de Prim constrói a MST (Minimum Spanning Tree) adicionando uma ligação de cada vez (a ligação parte entre os conjuntos resultados do corte do grafo). Enquanto que o método de Kruskal constrói a árvore ligação a ligação, mas fá-lo encontrando a ligação que une duas árvores numa floresta de MSTs.
O algoritmo inicia-se com uma floresta de V árvores (cada uma contendo unicamente um vértice) e com a ordenação das ligações por custo. É um método baseado nas ligações e é um algoritmo ganancioso (greedy).
Eficácia: Representando com uma matriz de adjacência:
- Com pesquisa baseada numa estrutura simples de dados: O(E log E).
- Com a utilização de filas de espera com prioridades: O(E + X log V)