检查根节点切割JAVA

Question

我想改变这段代码来检查根节点是否是一个切割节点。如果在DFS树中拥有多个子项，则根是仅限于节点的切割节点。如果我们检测到根节点是切割节点，则打印出来。我知道我需要更多的装饰，我只是在寻找一些输入。

到目前为止的代码：

public static void dfsDriver(AdjacencyListGraph g) { 

     startTimeClock = 1; 

     v = some arbitrary vertex in the graph (such as vertex “A”) 

     dfs(v); 

    } 



private static void dfs(Vertex v) { 

     v.setLabel(VISITED); 

     v.put(START_TIME, startTimeClock++); 


     for (Edge e: graph.incidentEdges(v)) { 

       Vertex w = graph.opposite(v, e); 

       if (w.get(DFS_STATUS) != VISITED) { 

        w.put(PARENT, v); 

        dfs(w); 

       } 
       else { 
         ; // edge e=(v,w) is either a dotted non-tree edge, or w is parent of v 
       } 
     } 
}  

Answer 1

您可能只需要这个测试：

boolean isCutRoot(Vertex root) { 
    final Edge[] rootEdges = graph.incidentEdges(root); 
    return rootEdges != null && rootEdges.length >= 2; 
} 

但是，如果有可能从根本上多条边指向同一个顶点，你需要修改上述方法来检查rootEdges中的边是否引用至少2个不同的顶点。