Please enable JavaScript.
Coggle requires JavaScript to display documents.
M14 - Coggle Diagram
M14
Algoritmo de Prim
Tem aplicações diretas no projeto de todos os tipos de redes – incluindo comunicação, informática, transporte e elétrica – fornecendo a maneira mais barata de obter conectividade.
Tem sido usado para fins de classificação em arqueologia, biologia, sociologia e outras ciências. Também é útil para construir soluções aproximadas para problemas mais difíceis, como o problema do caixeiro viajante
Se tal gráfico tiver pesos atribuídos às suas arestas, uma árvore geradora mínima é sua árvore geradora de menor peso, onde o peso de uma árvore é definido como a soma dos pesos em todas as suas arestas.
é mais difícil do que encontrar uma árvore geradora mínima para um grafo ponderado usando um dos vários algoritmos eficientes disponíveis para este problema.
A árvore gerada pelo algoritmo é obtida como o conjunto de arestas utilizadas para as expansões da árvore.
Algoritmo de Kruskal
O algoritmo de Kruskal analisa uma árvore geradora mínima de um grafo conectado ponderado G = V,E como um subgrafo acíclico com |V | − 1 arestas para as quais a soma dos pesos das arestas é a menor.
o algoritmo constrói uma árvore geradora mínima como uma sequência em expansão de subgrafos que são sempre acíclicos, mas não estão necessariamente conectados nos estágios intermediários do algoritmo.
O algoritmo começa classificando as arestas do gráfico em ordem não decrescente de seus pesos. Então, começando com o subgrafo vazio, ele varre essa lista ordenada, adicionando a próxima aresta da lista ao subgrafo atual se tal inclusão não criar um ciclo e simplesmente pulando a aresta.
-
-
A natureza do algoritmo de Prim torna necessário fornecer a cada vértice que não está na árvore atual a informação sobre a aresta mais curta que conecta o vértice a um vértice da árvore.