在线性时间内从具有 "very few" 条边的图构建 MST
Building MST from a graph with "very few" edges in linear time
我正在面试，面试官问了我一个问题：
我们有一个图 G(V,E)，我们可以使用 prim 或 kruskal 算法找到 MST。但是这些算法没有考虑到G中有"very few"条边。我们如何利用这些信息来提高寻找MST的时间复杂度呢？我们能在线性时间内找到 MST 吗？
我唯一记得的是 Kruskal 的算法在稀疏图中更快，而 Prim 的算法在真正密集的图中更快。但是我无法回答他如何利用关于边数的先验知识在线性时间内做出MST。
如有任何见解或解决方案，我们将不胜感激。
Kruskal 算法在边排序后几乎是线性的。如果使用像 disjoint set forest 这样的联合查找结构，处理单条边的复杂度将按 lg*(n) 的顺序排列，其中 n 是顶点的数量，并且此函数增长如此缓慢，以至于对于这种情况可以视为常数。然而，问题是要对边缘进行排序，您仍然需要 O(m * log(m))。其中 m 是边数。
Prim 的算法将无法利用边缘很少的事实。
您可以使用的一种方法类似于 'reversed' MST 方法，您从所有边开始并删除 最长 边，直到图形断开连接。你一直这样做，直到只剩下 n - 1 条边。仍请注意，仅当要删除的边数 k 足够少以至于 k * n < m * log(m).
时，这才会比 Kruskal 更好
假设|E| = |V| +c ,c 是一个小常数。您可以在图上 运行 DFS，每次检测到圆时，删除最大的边。你必须这样做 c +1 次。 O(c+1 * |E|) = O(E) 理论上的线性时间。
我正在面试，面试官问了我一个问题：
我们有一个图 G(V,E)，我们可以使用 prim 或 kruskal 算法找到 MST。但是这些算法没有考虑到G中有"very few"条边。我们如何利用这些信息来提高寻找MST的时间复杂度呢？我们能在线性时间内找到 MST 吗？
我唯一记得的是 Kruskal 的算法在稀疏图中更快，而 Prim 的算法在真正密集的图中更快。但是我无法回答他如何利用关于边数的先验知识在线性时间内做出MST。
如有任何见解或解决方案，我们将不胜感激。
Kruskal 算法在边排序后几乎是线性的。如果使用像 disjoint set forest 这样的联合查找结构，处理单条边的复杂度将按 lg*(n) 的顺序排列，其中 n 是顶点的数量，并且此函数增长如此缓慢，以至于对于这种情况可以视为常数。然而，问题是要对边缘进行排序，您仍然需要 O(m * log(m))。其中 m 是边数。
Prim 的算法将无法利用边缘很少的事实。
您可以使用的一种方法类似于 'reversed' MST 方法，您从所有边开始并删除 最长 边，直到图形断开连接。你一直这样做，直到只剩下 n - 1 条边。仍请注意，仅当要删除的边数 k 足够少以至于 k * n < m * log(m).
假设|E| = |V| +c ,c 是一个小常数。您可以在图上 运行 DFS，每次检测到圆时，删除最大的边。你必须这样做 c +1 次。 O(c+1 * |E|) = O(E) 理论上的线性时间。