0

私はこの問題を解決しようとしていますが、グラフにはかなり慣れていません。これを理解するために BFS を試しましたが、正しい答えが得られません。

私は何を間違っていますか？また、私が使用しているアプローチ以外に、これを行うより良い方法はありますか。

public static boolean isThereARoute(int[][] graph ,gNode n1 , gNode n2 ) {
    // where can we move? - anywhere where the value of x and y is 1 - else can't move
    // Start with node 1 and then traverse either BFS or DFS to see if the n2 is in the path anywhere

    // using BFS.

    //mark the ones where we can move as true
    boolean[][] canMove= new boolean[graph.length][graph[0].length]; 
    for(int i = 0;i<canMove.length;i++){
        for(int j =0;j<canMove[0].length;j++){
            if(graph[i][j]==-1){
                canMove[i][j] = false;
            }else{
                canMove[i][j] = true;
            }
        }
    }



    // create a queue
    Deque<gNode> queue = new LinkedList<gNode>();
    // insert the first node into the queue
    queue.add(n1);


    while(!queue.isEmpty()){
        gNode top = queue.poll();
        int x = top.x1;
        int y = top.y1;
        // only check the ones where we can go

        if( ( top.x1>=0 && top.x1<= graph.length-1) && (top.y1>=0 && top.y1<= (graph[0].length-1)) ){

            if(canMove[top.x1][top.y1]){

                if((top.x1 == n2.x1) && (top.y1 == n2.y1)){
                    // found our node;
                    return true;
                }

                // else haven't found any - add the nodes to the queue // allowed diagonals as well// therefore for each node 
                // there can be 8 neighbors
                queue.add(new gNode(x-1,y));
                queue.add(new gNode(x,y-1));
                queue.add(new gNode(x+1,y));
                queue.add(new gNode(x,y+1));
                queue.add(new gNode(x-1,y-1));
                queue.add(new gNode(x-1,y+1));
                queue.add(new gNode(x+1,y+1));
                queue.add(new gNode(x+1,y-1));

            }

        }

    }

    return false;
}

そして、チェックのために-

        int[][] graphD = new int[][]{

        {-1, 1,-1,-1,-1},
        {-1,-1, 1,-1,-1},
        {-1,-1, 1, 1,-1},
        {-1,-1,-1,-1,-1},
        { 1,-1, 1,-1,-1}
    };

    ArrayList<gNode> nodes = new ArrayList<gNode>();
    nodes.add(new gNode(0,0));//node A
    nodes.add(new gNode(1,1)); // node B
    nodes.add(new gNode(2,2)); // node C
    nodes.add(new gNode(3,3)); // node D
    nodes.add(new gNode(4,4)); // node E

    /**
     *  A->b
     * B->C
     * C->C
     * C->D
     * E-A
     * 
     */ 

    System.out.println(" is A -B connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(1)));
    System.out.println(" is A -D connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(3)));
    System.out.println(" is C -A connected?"+isThereARoute(graphD, nodes.get(3), nodes.get(0)));
    System.out.println(" is A -E connected?"+isThereARoute(graphD, nodes.get(0), nodes.get(4)));
    System.out.println(" is C -C connected?"+isThereARoute(graphD, nodes.get(2), nodes.get(2)));
4

3 に答える 3

1

言語に精通していない場合、10 ～ 20 行以上のコードをデバッグするのは苦手です。ただし、x から始まる BFS または DFS だけでなく、2 つのノード x と y の間にパスがあるかどうかを判断するためのより良い全体的なアプローチがあると言えます。つまり、x から順方向に BFS を実行し、同時に y から逆方向に BFS を実行できます。つまり、k=1 から始めて、<= k エッジのパスを使用して x から前方に移動して到達できるすべての頂点を見つけ、<= k エッジを使用して y から逆方向に移動して到達できるすべての頂点を見つけ、適用します。 k を 1 ずつ増やす基本的な BFS 原則。k ごとに、x から到達できる頂点をハッシュし、y から到達できる頂点をハッシュし、2 つのセット間で w が一致する場合、w は中点です。 x から y へのパス、したがって、パスが存在します。これが x から始まる BFS よりも好ましい理由は、x から y へのパスの長さが K の場合、x から始まる BFS は、K ステップで到達可能なすべてのノードを見つけるためです。 K）。しかし、私が提案した方法でそれを行うと、k >= K/2 に達したときに終了することができ、K/2 ステップで到達可能な頂点の 2 つのセットは、K ステップで到達可能な頂点のセットよりもはるかに小さくなることがよくあります。 . したがって、パスが存在する場合は、通常、私が提案した方法よりもはるかに速く見つけることができます。また、K/2 ステップで到達可能な頂点の 2 セットは、K ステップで到達可能な頂点のセットよりもはるかに小さいことがよくあります。したがって、パスが存在する場合は、通常、私が提案した方法よりもはるかに速く見つけることができます。また、K/2 ステップで到達可能な頂点の 2 セットは、K ステップで到達可能な頂点のセットよりもはるかに小さいことがよくあります。したがって、パスが存在する場合は、通常、私が提案した方法よりもはるかに速く見つけることができます。

于 2013-07-19T00:10:14.493 に答える
1

BFS はここで適用するのに適したアルゴリズムであると言えます。そのため、BFS コードの問題にすぎません。Adjacency Matrixでのグラフの表現方法について混乱しているようです。

            if((top.x1 == n2.x1) && (top.y1 == n2.y1)){
                // found our node;
                return true;
            }

これは、隣接行列 (エッジ) の特定のエントリに到達したかどうかを確認していますが、特定のノードに到達可能かどうかを確認するだけです。

gNode単一のインデックスを使用するように表現を変更し (または単に削除してint代わりに使用し)、隣接行列の値に基づいて最初のノードから BFS を実行する必要があります。

アルゴリズム/データ構造を理解するために追加のヘルプが必要な場合は、次のページが参考になると思われます: Adjacency matrices, BFS, DFS .

于 2013-07-19T00:01:08.060 に答える
-1

これにアプローチすることができます。

1. BFS (most simple and efficient too)
2. Transitive closure (found using Floyd-Warshall algorithm).
于 2013-07-19T09:17:33.880 に答える