O que é uma árvore geradora mínima?

É um subconjunto das arestas de um grafo que conecta todos os nós entre si, não contém ciclos, e tem o menor peso total possível de arestas entre todos esses subconjuntos conectores.

Como funciona o algoritmo de Kruskal?

Ele ordena todas as arestas por peso do menor para o maior, depois as processa em ordem, adicionando cada aresta à árvore apenas se ela conectar duas partes previamente desconectadas do grafo (verificado eficientemente com uma estrutura union-find).

Para que serve union-find?

Union-find (também chamado conjunto disjunto) rastreia eficientemente quais nós já estão conectados, permitindo que o algoritmo de Kruskal detecte rapidamente se adicionar uma aresta criaria um ciclo, sem reescanear toda a árvore a cada vez.

E se meu grafo estiver desconectado?

A calculadora relata uma floresta geradora mínima em vez disso — a forma mais barata de conectar internamente cada componente desconectado, já que nenhuma árvore única pode abranger nós que não têm caminho entre si.

A árvore geradora mínima é sempre única?

Não necessariamente — se várias arestas compartilham o mesmo peso, pode haver mais de uma árvore geradora mínima válida com o mesmo peso total, embora o peso total em si seja sempre único.

Como isso difere do algoritmo de Dijkstra?

Uma árvore geradora mínima minimiza o custo total para conectar todos os nós entre si, enquanto o algoritmo de Dijkstra minimiza o custo de um caminho entre dois nós específicos — os dois problemas resolvem perguntas diferentes mesmo que ambos trabalhem com grafos ponderados.

Quantos nós esta calculadora consegue processar?

Esta calculadora suporta até 50 nós, mais do que suficiente para exemplos de grafos inseridos manualmente enquanto mantém instantâneo o cálculo de ordenação e union-find.

Onde as árvores geradoras mínimas são usadas na vida real?

São usadas para projetar redes de custo eficiente — traçar rotas de cabos ou tubulações, fiar placas de circuito, agrupar pontos de dados, e aproximar soluções para problemas mais difíceis de design de rede.

Calculadora de Árvore Geradora Mínima — Encontre a Forma Mais Barata de Conectar um Grafo

Nossa Calculadora de Árvore Geradora Mínima encontra o conjunto de arestas que conecta todos os nós de um grafo ponderado ao menor custo total possível, usando o algoritmo de Kruskal com detecção de ciclos via union-find, dado seu grafo como uma lista de arestas em texto simples (ex. A-B:4, B-C:2).

Resposta rápida

Digite seu grafo ponderado como uma lista de arestas para encontrar instantaneamente a árvore geradora mínima — o conjunto mais barato de arestas conectando todos os nós — via o algoritmo de Kruskal.

Arestas (separadas por vírgula)

Digite arestas ponderadas como NóA-NóB:peso, ex. A-B:4, B-C:2.

Como usar Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online

1
Digite seu grafo como uma lista de arestas separadas por vírgula, ex. A-B:4, B-C:2.
2
Clique em 'Calcular' para encontrar a árvore geradora mínima.
3
Revise as arestas selecionadas e o peso mínimo total.

Por que usar Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online?

Uma árvore geradora mínima conecta todos os nós de um grafo usando o menor número e as arestas mais baratas possíveis, sem ciclos — exatamente a estrutura que você desejaria ao projetar uma rede (estradas, tubulações, fiação de circuitos) que deve alcançar cada ponto ao menor custo total. O algoritmo de Kruskal a encontra com elegância: ordena todas as arestas da mais barata para a mais cara, e adiciona gulosamente cada aresta que não cria um ciclo, rastreando a conectividade eficientemente com uma estrutura de dados union-find. Essa abordagem gulosa é comprovadamente ótima, e esta calculadora a executa diretamente em um grafo que você insere como uma lista de arestas ponderadas.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Caminho Mais Curto de Dijkstra — Grafos Ponderados Online

Encontre o caminho mais curto e a distância total entre dois nós em um grafo ponderado usando o algoritmo de Dijkstra. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Matriz de Adjacência — Construa uma Matriz de Grafo Online

Construa e exiba a matriz de adjacência de um grafo a partir de uma entrada simples de lista de arestas, junto com sua sequência de graus. Calculadora gratuita, ponderada ou não ponderada.

Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online

Colora os vértices de um grafo de modo que nenhum dois nós conectados compartilhem uma cor, usando o algoritmo guloso de Welsh-Powell. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Fluxo de Rede — Fluxo Máximo via Edmonds-Karp Online

Encontre o fluxo máximo de uma origem a um destino em um grafo direcionado com capacidades usando o algoritmo de Edmonds-Karp. Calculadora gratuita com uma lista de arestas simples.