Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal - Coggle Diagram
Algoritmo de Prim
Como funciona?
-
A subárvore inicial em tal sequência consiste em um único vertice selecionado arbitrariamente do conjunto V de vértices do gráfico
Em cada iteração, o algoritmo expande a árvore atual de maneira gananciosa, simplesmente anexando a
é o vértice mais próximo que não está nessa árvore.
-
o número total de tais iterações
é n - 1, onde n é o número de vértices no gráfico
Torna necessário fornecer a cada vértice que não está na árvore atual as informações sobre a aresta mais curta conectando o vértice a um vértice da árvore.
-
Anexando dois rótulos a um vértice: o nome do vértice da árvore mais próximo e o comprimento (o peso) da aresta correspondente
O que faz?
Encontra a árvore geradora mínima de um grafo ponderado, não-direcionado e conexo
-
-
Algoritmo de Kruskal
Como funciona
-
Então, começando com o subgrafo vazio, ele examina esta lista classificada, adicionar a próxima borda da lista ao subgráfico atual se tal inclusão não criar um ciclo e simplesmente pular a borda de outra forma
constrói uma árvore de abrangência mínima como uma sequência de expansão de
subgráficos que são sempre acíclicos