algorithm - 如果使用 BFS 检查添加边是否会创建循环，那么克鲁斯卡尔算法的总体大 O 运行时间是多少？

Question

如果使用 BFS 实现 Kruskal 算法来检查是否添加一条边并创建一个循环，那么该算法的整体 Big-O 运行时间是多少？

Answer 1

会的O(V * E + E * log E)。每个 BFS 都需要O(V)时间，因为树中有V - 1边（如果树还没有完全构建，则更少）并且它针对每个边运行（V是顶点数，E是边数）。所以O(V * E)总的来说。E * log E术语来自对边缘进行排序。