Peso árvore expansão Kruskal
- Created by
- Renato Passos, Eng. de Software
- Reviewed by
- Renato Passos, Eng. de Software
Last updated: Apr 18, 2026
About this calculator
The 'Kruskal Minimum Spanning Tree Weight' calculator computes the total weight of a minimum spanning tree in a graph using Kruskal's algorithm. This method selects the smallest-weight edges one by one, ensuring they don't form cycles, until all nodes are connected.
The algorithm works by sorting all edges in ascending order of weight. It then iterates through the edges, adding those that don't create cycles, until all vertices are connected. The result is the lowest total weight required to join the graph.
It is useful for optimization problems like telecommunications networks, power lines, or transportation, where the goal is the most efficient connection. Ensure the input graph is connected and has defined weights for all edges.
If edges share the same weight, the algorithm will still work, but multiple valid solutions may exist. Always verify input data to avoid errors in critical calculations.
Frequently asked questions
How does Kruskal's algorithm differ from Prim's?
Kruskal starts with edges sorted by weight, while Prim begins with a vertex and expands to the lowest-cost one. Both solve minimum spanning trees, but Kruskal is more efficient for sparse graphs.
What happens if the input graph is not connected?
The algorithm will generate a minimum spanning forest instead of a single tree. Ensure the graph is connected for the correct solution.
Does the calculator handle negative edge weights?
No, Kruskal's algorithm requires positive weights. Negative values may cause errors or invalid solutions.
Can I use this for directed graphs?
No, Kruskal's algorithm works only for undirected graphs. For directed graphs, use the Chu-Liu/Edmonds algorithm.