Implementation (Part 2)
Lição 6 de 9 do curso Algoritmo de Kruskal - Algoritmos de Grafos da Coddy.
Agora adicione a aresta segura de menor custo até que a MST esteja completa.
Desafio
MédioAgora construa a MST.
Escreva uma função chamada kruskal que receba n e o array plano edges (triplas, não direcionadas) de um grafo conectado, e retorne o peso total de sua Árvore Geradora Mínima (Minimum Spanning Tree).
Repetidamente pegue a aresta não utilizada mais barata; se seus pontos finais estiverem em conjuntos diferentes, una-os e adicione seu peso; caso contrário, pule-a.
Reutilize a ideia de union-find da lição anterior.
Experimente você mesmo
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Escreva o código aqui
return 0;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Kruskal - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity