删除最小数量的节点以使图断开连接

Question

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

Answer 1

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