Introduction

Bem-vindo de volta à série de Algoritmos de Grafos! Uma Árvore Geradora Mínima (MST) conecta todos os vértices de um grafo ponderado usando o menor peso total de arestas possível, sem ciclos.

O Algoritmo de Kruskal constrói a MST de forma gulosa: ele ordena as arestas da mais barata para a mais cara e adiciona cada uma, desde que não crie um ciclo. O truque para detectar ciclos rapidamente é uma estrutura de dados chamada union-find (também conhecida como conjunto disjunto).

O grafo é não direcionado e ponderado, fornecido como n (vértices 0 a n - 1) and edges, um array plano de triplas [u0, v0, w0, ...] para uma aresta não direcionada u - v de peso w.

Vamos começar!