我试图写一个方法来找出一个无向图的顶点之间是否存在一条路径,这个无向图用邻接矩阵来表示。
这是我得到的邻接矩阵:
int[][] adj_matrix ={{0,1,0,0},
{1,0,1,0},
{0,1,0,1},
{0,0,0,0}};
这就是我迄今为止所尝试的:
public boolean isPath(int vorigin, int vdestiny)
{
boolean result = false;
ArrayList path = new ArrayList<Integer>();
for (int i = 0; i < adj_matrix.length; i++) {
for (int j = 0; j < adj_matrix.length; j++) {
if(adj_matrix[vorigin][j]>0){
path.add(vorigin);
}
if(adj_matrix[vdestiny][j]>0){
path.add(vdestiny);
break;
}
}
}
if(path.contains(vorigin) && path.contains(vdestiny)){
System.out.println("There is a path");
}
return result;
}
如您所见,我的方法只检查每个vertix所在的行,因此它实际上不起作用。我不知道该怎么办。我真的不知道如何检查顶点,它确实是路径的一部分。
我已经对此做了很多研究,但是我找到的大多数方法都实现了邻接列表,这是我不想在本例中使用的。其他一些方法使用递归,这是一个很好的选择,但我想用一种迭代的方式。提前谢谢。
1条答案
按热度按时间mnemlml81#
下面是java程序的源代码,用于查找两个给定节点之间是否存在路径。该java程序已在windows系统上成功编译并运行。程序输出如下所示。
输出: