Calculadora de árvore geradora mínima (Kruskal / Prim)

Calculadora de árvore geradora mínima (Kruskal / Prim) | Ferramenta online grátis | Elysia Tools

Guia de uso da ferramenta

Veja quando usar esta ferramenta, o que ela suporta e como os usuários a aplicam.

Fatos principais

Categoria: Math & Numbers
Tipos de entrada: textarea, select, text, number
Tipo de saída: text
Cobertura de exemplos: 4
API pronta: Sim

Visão geral

Calcule a árvore geradora mínima (AGM) de grafos não dirigidos ponderados utilizando os algoritmos clássicos de Kruskal ou Prim. A ferramenta processa listas de arestas com pesos positivos ou negativos, ignora laços automaticamente e exibe o passo a passo completo da formação da árvore com validação de conectividade.

Quando usar

Quando você precisa encontrar o subconjunto de menor custo total para conectar todos os vértices de uma rede.
Ao estudar ou lecionar teoria dos grafos e precisar visualizar a detecção de ciclos por união-busca ou o crescimento de componentes.
Para verificar exercícios acadêmicos de algoritmos gulosos comparando a ordem de seleção dos métodos de Kruskal e Prim.

Como funciona

1Insira as arestas do grafo informando dois identificadores de nós e o peso correspondente em cada linha.
2Selecione o algoritmo desejado (Kruskal com união-busca ou Prim com expansão de vértice) e, se aplicável, o nó inicial para o método de Prim.
3Ajuste a precisão das casas decimais dos pesos numéricos conforme a necessidade do cálculo.
4A ferramenta processa o grafo, descarta arestas que geram ciclos ou laços e exibe o registro detalhado de decisões junto com o peso total final.

Casos de uso

Planejamento de rotas de cabeamento de fibra óptica ou infraestrutura elétrica entre múltiplos terminais ao menor custo.
Conferência de passos de execução e rejeições de ciclos em listas de exercícios de estruturas de dados e matemática discreta.
Otimização de conexões e enlaces redundantes em topologias de redes de computadores com nós distribuídos.

Exemplos

1. Execução com algoritmo de Kruskal

Estudante de Ciência da Computação

Contexto

Precisa conferir a resolução de um trabalho acadêmico sobre o algoritmo de Kruskal e a estrutura Union-Find.

Problema

Verificar quais arestas são aceitas e quais são descartadas por fecharem ciclos em um grafo de 6 nós.

Como usar

Insira a lista de 8 arestas no campo de texto, selecione o algoritmo 'Kruskal' e clique para calcular.

A B 4
A C 2
B C 5
B D 10
C E 3
D E 4
D F 11
E F 8

Resultado

Exibição do registro ordenado com a rejeição da aresta B—C por ciclo e seleção de 5 arestas com peso total 21.

2. Crescimento de componentes com Prim

Professor de Algoritmos

Contexto

Deseja demonstrar em sala de aula como o algoritmo de Prim expande a árvore a partir de um vértice específico.

Problema

Exibir a sequência exata de nós adicionados ao componente partindo do nó inicial D.

Como usar

Cole as arestas da rede, selecione o algoritmo 'Prim' e defina 'D' no campo de nó inicial.

Perguntas frequentes

Qual é o limite de arestas suportado pela calculadora?

A ferramenta suporta grafos não dirigidos contendo de 1 a 30 arestas.

O que acontece se o grafo for desconectado?

O cálculo é interrompido e a ferramenta emite um aviso indicando a quantidade de componentes conexos encontrados.

Pesos negativos são permitidos nas arestas?

Sim, tanto Kruskal quanto Prim aceitam arestas com valores de peso negativos.

Como a ferramenta lida com laços (arestas que ligam um nó a ele mesmo)?

Laços são automaticamente detectados e ignorados durante a execução dos algoritmos.

Os algoritmos de Kruskal e Prim geram o mesmo custo total?

Sim, ambos produzem exatamente o mesmo peso total para a árvore geradora mínima de um mesmo grafo conexo.

A B 4
A C 2
B C 5
B D 10
C E 3
D E 4
D F 11
E F 8

Executar esta ferramenta

Exemplos compatíveis com esta ferramenta

Continue com ferramentas e temas relacionados

Veja quando usar esta ferramenta, o que ela suporta e como os usuários a aplicam.

Fatos principais

Visão geral

Quando usar

Como funciona

Casos de uso

Exemplos

1. Execução com algoritmo de Kruskal

2. Crescimento de componentes com Prim

Perguntas frequentes

Exemplos de Processamento de Imagem Web Python

Exemplos SVG

Exemplos de Processamento de Imagem Android Java

Exemplos de Processamento de Imagem Android Kotlin

Calculadora de Densidade (ρ = m/V)

Calculadora de NPSH de Bomba (Altura Líquida Positiva de Sucção) e Verificação de Cavitação

Palavras para Número

Marca d’água discreta adaptativa de 12 pontos