无向图中关键节点的数量

Question

无向图中关键节点的数量

graphdepth-first-search

4

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

当移除一个节点后，使得该图不连通的节点称为关键节点。目标是查找图中关键节点的数量。

解决方案如下：

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

这个解决方案的时间复杂度是O(N*E)，或者最坏情况下是O(N^3)。

是否有O(N^2)的解决方案或O(E)的解决方案呢？因为N^3有点慢。

- Sr1n4th

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Khaled.K · Accepted Answer

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

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

一个可能的解决方案如下：

对于图G中的每个节点i： 1. 列表L：所有直接与节点i相连的节点 2. 如果存在列表L中的两个节点u和v，使得没有路径可以通过i连接u和v，则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;
    }
}