graph - 无向图中关键节点的数量

Question

我有一个包含 N 个节点和 E 个边的图 G。每条边都是无方向的。目标是找到没有。的关键节点。

删除时使图断开连接的节点称为关键节点。
目标是找到没有。图中这样的节点。

一个解决方案是:-

对于属于图中的每个节点，
从图表中删除它，
从剩余的图中选择一个节点，
执行dfs，
如果我们能够到达任何地方，那么它就不是关键节点。

这个解决方案是 O(N*E) 或最坏情况 O(N^3)。

是否有 O(N^2) 解决方案或 O(E) 解决方案，因为 N^3 有点太慢了。

Answer 1

关键节点是一个节点，当被移除时，会将图切割成 2 个或更多不相交的子图..

因此，关键节点是连接到仅通过该关键节点连接的2个或更多子图的节点 ..

一个可能的解决方案可能是这样的:

对于图 G 中的每个节点 i:

列表L:直接连接到节点i的所有节点

如果在列表 L 中存在 2 个节点 u 和 v 使得没有路径通过 v 而不是 i 连接 u，则 i 是关键节点

引用: Wikipedia:Cycle Detection

示例(在 Java 中):

public class CrucialNode
{
    public static ArrayList<Node> crucialVertices (Graph g)
    {
        ArrayList<Node> crucial = new ArrayList<Node> ();

        for (Node n : g.getV()) if (isCrucial(g,n)) crucial.add(n);

        return crucial;
    }

    public static boolean isCrucial (Graph g, Node n)
    {
        Graph h = new Graph(g);

        h.removeVertex(n);

        for (Node u : n.getNext())
        {
            for (Node v : n.getNext())
            {
                if (u.equals(v)) continue;

                if (!h.connected(u,v)) return true;
            }
        }

        return false;
    }
}