Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm, Kruskal’s Algorithm - Coggle Diagram
Prim's Algorithm
-
-
-
Algorithm
// Prim's algorithm para a construção de minimum spanning tree.
Input: Um grafo com pesos e conectado
Output: Et, the set od edges composing a minimum spanning tree of G
Vt <- {v0} // O conj. de tree vert. pode ser inicializado com algum vert.
Et <- Vazio
for i<-1 to |V| - 1do
find a minimum-weight edge e = (v,u) entre todos os vert.(v,u) cada um que v é em Vt e un é em V - Vt
Vt <- Vt U {u}
Et<- Et U {e}
return *Et
O natural do algoritmo é fazer o necessário para fornecer cada vert. nque não está na current tree com informações sobre a menor aresta conectada ao vert. com a tree vert..
-
Kruskal’s Algorithm
É um algoritmo que visa encontrar uma minimum spanning tree em um grafo conexo, ponderado ou não.
O algoritmo constrói um minimum spanning tree como uma expansão de sequências de subgrafos que são sempre Acíclicos, mas não são necessariamente conectados por um estágio intermediário do algoritmo.
O algoritmo começa pela ordenação do grafo de arestas em ordem não decrescente dos pesos deles. Logo, começamos pelo subgrafo vazio, visualizamos está lista ordenada, e add a próx. aresta na lista para o sbugrafo corrent. Caso, cada ums inclusão não criar um ciclo e simplesmente pule para a próx. aresta.
Algoritmo
//Kruskal's algorith m para construção de um minimum spanning tree
//Input: Um grafo pesado e conectado
//Output: Et, o conj. de arestas compostas pelo um minimum spanning tree do grafo G ordenado E em ordem não decrescente dos pesos das arestas
Et<-vazio; ecounter<-0
k<-0
while ecounter < |V| - 1 do
k++;
if Et U {eik} is acyclic
Et<-Et U {eik}; ecounter++;
return Et
A priore temos a impressão de que o algoritmo de Kruskal é mais simples que o de Prim's. Porém não é vdd, pois emos que checar se a nova add de aresta formaria um ciclo.
é importante notar que cada componente conectado de um subgrafo gerado por Kruskal's é uma tree por que não apresente ciclos.
Com todos esses pontos levantados, é conveniente usarmos uma versão ligeiramente diferente da interpretação de Kruskal's algorithm.
Podemos considerar que as operações do algoritmo são como uma progressão por meio de uma série de florestas que contém todos os vert. do grfoe algumas das arestas.
A floresta inicial consiste de trivial trees, cada uam formada por um único vert. do grafo. A floresta final consiste em uma única tree que é uma minimum spanning tree do grafo. E em cada iteração, o algoritmo acrescente a próx. aresta(u,v) da lista ordenada do grafo de arestas.
-
-
-