参考 java查找无向连通图中两点间所有路径的算法,对代码进行了部分修改,并编写了测试用例。
算法要求:
1.在一个无向连通图中求出两个给定点之间的所有路径;
2.在所得路径上不能含有环路或重复的点;
算法思想描述:
1.整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身);
2.定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一 个与起始节点直接相连的节点,求解它到终点的所有路径(路径上不包括起始节点)得到一个路径集合,将这些路径集合相加就可以得到起始节点到终点的所有路径;依次类推就可以应用递归的思想,层层递归直到终点,若发现希望得到的一条路径,则转储并打印输出;若发现环路,或发现死路,则停止寻路并返回;
3.用栈保存当前已经寻到的路径(不是完整路径)上的节点,在每一次寻到完整路径时弹出栈顶节点;而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点,从而实现回溯。
实现代码
1.Node.java
importjava.util.ArrayList;
/*表示一个节点以及和这个节点相连的所有节点*/
publicclassNode
{
publicStringname=null;
publicArrayListrelationNodes=newArrayList();
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicArrayListgetRelationNodes(){
returnrelationNodes;
}
publicvoidsetRelationNodes(ArrayListrelationNodes){
this.relationNodes=relationNodes;
}
}
2.test.java
importjava.util.ArrayList;
importjava.util.Iterator;
importjava.util.Stack;
publicclasstest{
/*临时保存路径节点的栈*/
publicstaticStackstack=newStack();
/*存储路径的集合*/
publicstaticArrayList