Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim’s Algorithm, Algoritmo de Kruskal, Subconjuntos Disjuntos e…
Prim’s Algorithm
Definição
Árvore Geradora Mínima (MST): Uma árvore geradora de um grafo não direcionado e conectado é seu subgrafo acíclico conectado que contém todos os vértices do grafo. Se um grafo tem pesos atribuídos às suas arestas, uma MST é a árvore geradora com o menor peso total.
Algoritmo de Prim:
Constrói uma MST expandindo uma árvore inicial a partir de um único vértice e, a cada iteração, anexa o vértice mais próximo que ainda não está na árvore. O algoritmo termina quando todos os vértices foram incluídos.
Prova de Correção:
A prova de correção é baseada na indução, mostrando que a árvore gerada em cada passo é parte de uma MST do grafo original.
Algoritmo de Kruskal
Problema
Dado um grafo conectado e ponderado, encontrar a árvore geradora mínima (MST) que conecta todos os vértices com o menor custo total, sem formar ciclos.
Definição
Árvore Geradora Mínima (MST): Um subgrafo acíclico de um grafo que inclui todos os vértices com o menor peso total.
Algoritmo de Kruskal:
Um algoritmo guloso que constrói uma MST considerando um subgrafo acíclico com |V|-1 arestas, onde a soma dos pesos das arestas é mínima. O algoritmo começa ordenando as arestas em ordem crescente de peso e, em seguida, adiciona arestas ao subgrafo desde que não formem um ciclo.
-