给定一个有向图，找出是否有两个节点之间的路线 [英] Given a directed graph, find out whether there is a route between two nodes
问题描述
我试图解决这个问题，我是相当新的图形。 我试图BFS图了这一点，但我没有得到正确的答案。
我究竟做错了什么？此外，有没有这样做，比我现在用的方法等更好的办法。
公共静态布尔isThereARoute（INT [] []图，的GNode N1，N2的GNode）{
//我们在这里可以移动？ - 在任何地方，其中x和y的值是1 - 否则不能动
//开始与节点1，然后遍历无论是BFS或DFS，看看是否N2是在路径的任何地方
//使用BFS。
//标记的人，我们可以移动，真
布尔[] [] canMove =新的布尔[graph.length] [图表[0] .length]。
的for（int i = 0; I＆LT; canMove.length;我++）{
对于（INT J = 0; J＆LT; canMove [0] .length; J ++）{
如果（图[I] [J] == - 1）{
canMove [I] [J] = FALSE;
}其他{
canMove [I] [J] =真;
}
}
}
//创建一个队列
双端队列＆LT;的GNode＆GT;队列=新的LinkedList＆LT;的GNode＆GT;（）;
//插入第一个节点插入到队列
queue.add（n1）的;
而（！queue.isEmpty（））{
的GNode顶= queue.poll（）;
INT X = top.x1;
INT Y = top.y1;
//只检查那些在这里我们可以去
如果（（top.x1＆GT; = 0＆安培;＆安培; top.x1＆其中; = graph.length-1）及及（top.y1＆GT; = 0＆安培;＆安培; top.y1＆其中; =（图形[0]。长度-1）））{
如果（canMove [top.x1] [top.y1]）{
如果（（top.x1 == n2.x1）及及（top.y1 == n2.y1））{
//发现我们的节点;
返回true;
}
//其他还没有发现任何 - 添加节点到队列//允许对角线以及//因此为每个节点
//可以有8邻居
queue.add（新的GNode（X-1，Y））;
queue.add（新的GNode（X，Y-1））;
queue.add（新的GNode（X + 1，Y））;
queue.add（新的GNode（X，Y + 1））;
queue.add（新的GNode（X-1，Y-1））;
queue.add（新的GNode（X-1，Y + 1））;
queue.add（新的GNode（X + 1，Y + 1））;
queue.add（新的GNode（X + 1，Y-1））;
}
}
}
返回false;
}
和为入住
INT [] [] graphD =新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的＆LT;的GNode＆GT;节点=新的ArrayList＆LT;的GNode＆GT;（）;
nodes.add（新的GNode（0,0））; //节点A
nodes.add（新的GNode（1,1））; // B节点
nodes.add（新的GNode（2,2））; //节点C
nodes.add（新的GNode（3,3））; //节点D
nodes.add（新的GNode（4,4））; //节点E
/ **
* A-＆GT; b
* B-＆GT的温度
* C-＆GT的温度
* C-＆GT; d
* E-A
*
* /
的System.out.println（就是连接在A -B？+ isThereARoute（graphD，nodes.get（0），nodes.get（1）））;
的System.out.println（连接在-D？+ isThereARoute（graphD，nodes.get（0），nodes.get（3）））;
的System.out.println（为C -A有联系吗？+ isThereARoute（graphD，nodes.get（3），nodes.get（0）））;
的System.out.println（是连接A〜E？+ isThereARoute（graphD，nodes.get（0），nodes.get（4）））;
的System.out.println（为C -C连接？+ isThereARoute（graphD，nodes.get（2），nodes.get（2）））;
我会说，BFS是正确的算法适用于此，所以它只是一个与你的BFS code问题。它看起来像你困惑如何图表重新psented在邻接矩阵 $ P $。
IF（（top.x1 == n2.x1）及及（top.y1 == n2.y1））{
//发现我们的节点;
返回true;
}
这是检查是否在邻接矩阵（边缘）的特定条目已经达到，但你只是应该被检查，如果给定节点可以到达。
您应该改变你的的GNode 重presentation使用单一指数（或只是删除它，并使用 INT 代替），并做你从第一节点BFS基于关邻接矩阵值。
如果你需要一些额外的帮助与理解算法/数据结构，这个页面似乎是一个很好的参考：的邻接矩阵，BFS，DFS 。
I'm trying to solve this problem and i'm fairly new to graphs. I tried BFS to figure this out but i'm not getting the right answer.
What am i doing wrong? Also, is there a better way of doing this, other than the approach i am using.
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;
}
And for the check-
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)));
I would say that BFS is the right algorithm to apply here, so it's just a problem with your BFS code. It looks like you're confused about how graphs are represented in an Adjacency Matrix.
if((top.x1 == n2.x1) && (top.y1 == n2.y1)){
// found our node;
return true;
}
This is checking if a specific entry in the adjacency matrix (an edge) has been reached, but you're just supposed to be checking if a given node is reachable.
You should change your gNode representation to use a single index (or just drop it and use an int instead), and do your BFS from the first node based off the adjacency matrix values.
If you need some additional help with understanding the algorithm / data structures, this page seems like a good reference: Adjacency matrices, BFS, DFS.
这篇关于给定一个有向图，找出是否有两个节点之间的路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
