java - 在Java中检测未连接无向图中的循环

Question

我写了一个函数，每次我向图中添加一条边时都尝试检测一个循环（最终得到一个 MST） 该函数接收一个带有当前 MST 的列表，一个带有已访问边的列表和边缘的节点检查它是否使图形循环。该函数通过贪婪方法接收每个边缘（每次从最轻到最重的只有正加权边缘）

private boolean EdgeConnect(List<Edge> candidates_lst,List<Edge> visit, int start ,int end){
    if (start == end){
        return false;
    }
    for(int k = 0; k < candidates_lst.size(); k++){
        Edge edge = candidates_lst.get(k);
        int place_node;
        if (edge.node1 != end && edge.node2 != end) {
            place_node = 0;
        }
        if (edge.node1 == end) {
            place_node = 1;
        }
        else {
            place_node = 2;
        }
        if (place_node != 0 && !visit.contains(edge)){
            visit.add(candidates_lst.get(k));
            end = start;
            if(place_node == 1){
                end = edge.node1;
            }
            else{
                end = edge.node2;
            }
            if(EdgeConnect(candidates_lst,visit,start,end) == false){
                return false;
            }
        }
    }
    return true;
}

该函数通过了一些测试用例，但在其他测试用例失败。帮助将不胜感激:) 谢谢！

标签： javagraphgreedyminimum-spanning-tree