Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's algorithm, Kruskal's algoritm - Coggle Diagram
Prim's algorithm
Algoritmo
Escolhe-se um vértice arbitrario V para começar o algoritmo. Após isso, será adicionado à árvore o vértice mais pŕoximo de V
Em cada iteração, será adicionado outro vértice mais próximo que não esteja na árvore
Assim, até n-1 iterações, o algoritmo adicionará os n vértices na subárvore e formará uma spanning tree
Propósito
Dado um conjunto de pontos, conecte-os de modo que o caminho seja menos custoso possível
É aplicado na comunicação, computação, transporte, etc
Representação
Podemos visualizar esse problema como um grafo: os vértices representam os pontos e as arestas representam os pesos
Spanning tree
-
Grafo com peso: a spanning tree, nesse caso, é o grafo com o menor peso, sendo o peso a soma do custo de todas as arestas
-
Kruskal's algoritm
-
Algoritmo
-
-
-
Adição de elementos: O algoritmo adiciona as arestas em ordem crescente, desde que não crie um ciclo. Caso contrário, a aresta em específico simplesmente não é colocada