graph - 删除最小节点数以使图形断开连接

Question

找到使图断开连接需要删除的最小节点数（不存在从任何节点到所有其他节点的路径）。节点数可以是 10 ⁵

Answer 1

考虑无向图。

totalDegree = sum of degree of all nodes.
while(totalDegree > 0) {
    Remove the node with highest degree and it's edges.
    Update degree count of each node.
    totalDegree = sum of degree of all remaining nodes.
}
remaining nodes are all disconnected

试图考虑一个不会给出最小节点数的情况。

Answer 2

首先，要找到一个不需要使图连通的节点，您需要找到一个循环。一旦你找到一个循环，那么你就知道那些循环中的所有这些边都是不需要的。图中的所有剩余边都需要将图保持在一起，因此您对图进行简单的遍历并计算连接的顶点数以找到需要移除以使图断开连接的最小节点数。我不确定这是否是最有效的方式，只是我头脑中最有效的方式。如果 V 是顶点数并且 E 是边数，则时间复杂度将在 O(V + E) + O(V) 左右，因为初始循环查找是 O(V + E) 并且计数节点是 O(V)。由于 E >= V，时间复杂度可以四舍五入到 O(E)，但具有巨大的常数因子。