Peso árvore expansão Kruskal
- Criado por
- Renato Passos, Eng. de Software
- Revisado por
- Renato Passos, Eng. de Software
Última atualização: 18 de abr. de 2026
Sobre esta calculadora
A calculadora 'Peso árvore expansão Kruskal' calcula o peso total da árvore de expansão mínima em um grafo, aplicando o algoritmo de Kruskal. Esse método seleciona as arestas de menor peso, uma por uma, garantindo que não formem ciclos, até conectar todos os nós do grafo.
O algoritmo funciona ordenando todas as arestas do grafo por peso ascendente. Em seguida, ele itera sobre as arestas, adicionando aquelas que não formam ciclos, até que todas as vértices sejam conectadas. O resultado é a menor soma possível de pesos para unir o grafo.
É útil em problemas de otimização, como redes de telecomunicações, linhas de energia ou transporte, onde se busca a conexão mais eficiente. Atente-se para garantir que o grafo fornecido seja conexo e tenha pesos definidos para todas as arestas.
Caso o grafo tenha arestas com o mesmo peso, o algoritmo ainda funcionará, mas pode haver mais de uma solução válida. Sempre confirme os dados de entrada para evitar erros em cálculos críticos.
Perguntas frequentes
Como o algoritmo de Kruskal é diferente do de Prim?
Kruskal começa com arestas, ordenando-as por peso, enquanto Prim começa com um vértice e expande para o de menor custo. Ambos resolvem problemas de árvore mínima, mas Kruskal é mais eficiente em grafos esparsos.
O que acontece se o grafo fornecido não for conexo?
O algoritmo gerará uma floresta de árvores mínimas, mas não uma única árvore. Certifique-se de que o grafo esteja conectado para obter a solução correta.
A calculadora considera arestas de peso negativo?
Não, o algoritmo de Kruskal requer pesos positivos. Valores negativos podem causar erros ou soluções inválidas.
Posso usar essa calculadora para grafos direcionados?
Não, o algoritmo de Kruskal só funciona com grafos não direcionados. Para grafos direcionados, use o algoritmo de Chu-Liu/Edmonds.