Algoritmo de Kruskal

Nesta lição, ìremos discutir Árvores geradoras mínimas (MST) e o Algoritmo de Kruskal*.

Árvores geradoras mínimas (MST)

A teoria por detrás das árvores geradoras mínimas só faz sentido quando estamos trabalhando em grafos ponderados não direcionados. Uma árvore geradora é um subgrafo conexo e sem ciclos de um grafo não direcionado .

Chamemos o custo de uma árvore geradora de a soma dos pesos de todas as arestas que pertencem a essa árvore geradora. Com esta definição, somos capazes de definir o que é uma MST. A Árvore Geradora Mínima é a árvore geradora com custo mínimo.

Dada esta definição, há uma questão simples que devemos colocar-nos: como encontrar a MST de um grafo? Existem dois algoritmos para encontrá-la: Algoritmo de Kruskal e Algoritmo de Prim.

Nesta lição, cobriremos apenas o Algoritmo de Kruskal. Na próxima lição, aprenderemos sobre Algoritmo de Prim.

Agora vamos entender como Algoritmo de Kruskal encontra a MST de um grafo

Algoritmo de Kruskal

A ideia deste algoritmo é simples. Vamos iterar sobre as arestas do nosso grafo em ordem não decrescente dos pesos e construir a nossa MST aresta por aresta.

Suponha que estamos processando a -ésima aresta e que a MST atual é o grafo . Uma vez que é uma árvore, não pode ter ciclos. Portanto, se colocarmos o -ésima aresta em e ele formar um ciclo, então não a incluímos em . Caso contrário, adicionaremos ela em .