Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm, Kruskal's Algorithm - Coggle Diagram
Prim's Algorithm
Algoritmo
A subarvore inicial é um vértice unico selecionado arbitrariamente a partir do conjunto de vertices do grafo
A cada iteração o algoritmo expanda a arvore atual conectando-se ao vértice mais próximo que não esteja na árvore
-
O algoritmo para depois que todos os vértices do grafo forem inseridos na arvore que esta sendo construída
-
Como o algoritmo expande a arvore em um vértice a cada iteração o número de iterações é n-1 sendo n o número de vértices do grafo
Eficiência
Depende da estrutura de dados escolhida para o grafo e para a fila de prioridade do conjunto de distancias o qual prioridades dos vertices são as distâncias para os vértices mais próximos
Definições
Uma arvore geradora(Spanning tree) de um grafo conexo não direcionado consiste nos seus subgrafos aciclicos quew contem todos os vertices do grafo
Se esse grafo tiver pesos a arvore geradora com o menor peso, isto é a menor soma dos pesos em suas arestas é chamada de arvore geradora mínima(minimum spanning tree)
o problema da arvore geradora minima tem o objetivo de achar essa arvore para um dado grafo conexo com pesos
Kruskal's Algorithm
-
-
Algoritmo
Então começa com o subgrafo vazio escaneando-se a lista ordenada adicionando a próxima aresta na lista ao atual subgrafo
-
-
-