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：

  1. 列表 L：直接连接到节点 i 的所有节点

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

参考：维基百科：循环检测

示例（在 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;
    }
}