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 和 y 之间是否存在路径，而不仅仅是从 x 开始的 BFS 或 DFS。即，您可以从 x 开始正向进行 BFS，同时从 y 反向进行 BFS。即从 k=1 开始，您会发现所有可以使用 <= k 边的路径从 x 向前移动的顶点，并且您会找到所有可以使用 <= k 边从 y 反向移动的顶点，然后您应用将 k 增加 1 的基本 BFS 原则。对于每个 k，您对您可以从 x 到达的顶点进行哈希处理，并对您可以从 y 到达的顶点进行哈希处理，如果您在两组之间得到匹配 w，则 w 是中点从 x 到 y 的路径，所以存在路径。这比从 x 开始的 BFS 更可取的原因是，如果从 x 到 y 的路径长度为 K，那么从 x 开始的 BFS 会发现所有节点在 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 回答