Kruskal算法可以替换Prim算法。它使用数据结构“不相交集”来构建最小生成树，从权值最小的边开始有序地处理图中的所有边。Kruskal算法的性能是O(E log E)，如果不相交集这个结构实现得足够精巧，那么性能可能降到O(E log V)。算法的细节可以在（Cormen等，2001）中找到。