Please enable JavaScript.
Coggle requires JavaScript to display documents.
MINIMUM-COST SPANNING TREES - Coggle Diagram
MINIMUM-COST SPANNING TREES
Prim´s algorithm
Técnica utilizada em grafos ponderados para encontrar uma Árvore Geradora Mínima (AGM)
O algoritmo começa selecionando um nó inicial arbitrário e, a partir desse nó, expande a árvore de forma incremental
Em cada passo, seleciona-se a aresta de menor peso que conecta um nó pertencente à árvore atual a um nó fora dela. Isso garante que a árvore cresça de maneira a minimizar o custo total.
A aresta selecionada é adicionada à árvore, juntamente com o nó conectado por essa aresta. O processo continua até que todos os nós estejam na árvore, formando assim a Árvore Geradora Mínima.
Kruskal´s algorithm
usado para encontrar uma Árvore Geradora Mínima em um grafo ponderado
A principal diferença é que o algoritmo de Kruskal se baseia na ordenação das arestas por peso.
Todas as arestas do grafo são ordenadas em ordem crescente de peso.
As arestas são adicionadas à árvore geradora mínima uma por uma, começando pela aresta de menor peso.
A cada adição, verifica-se se a inclusão da aresta criaria um ciclo na árvore já construída. Se não criar, a aresta é adicionada.
Esse processo de seleção e inclusão de arestas continua até que a árvore geradora mínima seja formada, conectando todos os nós do grafo
Uma Árvore Geradora Mínima (AGM) é uma subárvore de um grafo conectado ponderado que conecta todos os nós com o menor custo total possível.
Essa árvore é "geradora" porque abrange todos os nós e "mínima" porque a soma dos pesos das arestas é minimizada.
Qualquer cenário em que seja necessário conectar vários pontos enquanto se mantém os custos baixos pode se beneficiar de uma AGM.
Distribuição eficiente de recursos
Planejamento de redes de comunicação
Design de rotas de transporte
Construção de redes elétricas