1

disjointsets の find/union メソッドを使用して、無向グラフでサイクル検出のコードを実装しています。

実装は次のとおりです。

public boolean isCyclicundirected(){
    int k;
    ArrayDisjointSet set = new ArrayDisjointSet(5);
    //Set<Vertex> parents = new HashSet<Vertex>();
    System.out.println(vertexMap);
    Set<String> allVertices = vertexMap.keySet();
    for (String v : allVertices){
        Iterator<Edge> e = vertexMap.get(v).adj.iterator();
        while (e.hasNext()){
            int i = Integer.parseInt(vertexMap.get(v).name);
            int j = Integer.parseInt(e.next().target.name);
            if (set.isConnected(i, j))
                return true;
            else
                   k = set.join(i, j);
            System.out.println(set);
    }
    }
    return false;
}

これisConnectedが disjoinset の

public boolean isConnected(int i, int j){
    return find(i)==find(j);
}

2 つのノードが同じルート ( によって返されるfind) を持っている場合、サイクルがあることを示します。サイクルがないこのようなグラフの場合(1,2),(2,3),(3,4)、私のメソッドは true を返します。何が悪いのか理解できていません。

最新の編集: 以下の提案の後:

public boolean isCyclicundirected() {
    int k;
    HashSet<HashSet<Vertex>> vertexpairs = new HashSet<HashSet<Vertex>>();
    ArrayDisjointSet set = new ArrayDisjointSet(100);
    Set<String> allVertices = vertexMap.keySet();
    for (String v : allVertices) {
        Vertex current = vertexMap.get(v);
        for (Edge e : current.adj){
            Vertex nextVertex = e.target;
            HashSet<Vertex> temp = new HashSet<Vertex>();
            temp.add(nextVertex);
            temp.add(current);

            if (!vertexpairs.contains(temp)) {
                vertexpairs.add(temp);
                int i = Integer.parseInt(current.name);
                int j = Integer.parseInt(nextVertex.name);
                if (set.isConnected(i, j))
                    return true;
                else
                    k = set.join(i, j);
                System.out.println(set);
            }
        }
    }
    return false;
}

私は得るnode:java.util.NoSuchElementException

4

1 に答える 1

2

両側から 1 回ずつ、各エッジを 2 回繰り返します。エッジを一度だけ考慮する必要があります。

于 2013-12-02T23:40:28.223 に答える