参考 ，对代码进行了部分修改，并编写了测试用例。
算法要求：
1. 在一个无向连通图中求出两个给定点之间的所有路径；
2. 在所得路径上不能含有环路或重复的点；
算法思想描述：
1. 整理节点间的关系，为每个节点建立一个集合，该集合中保存所有与该节点直接相连的节点（不包括该节点自身）；
2. 定义两点一个为起始节点，另一个为终点，求解两者之间的所有路径的问题可以被分解为如下所述的子问题：对每一 个与起始节点直接相连的节点，求解它到终点的所有路径（路径上不包括起始节点）得到一个路径集合，将这些路径集合相加就可以得到起始节点到终点的所有路径；依次类推就可以应用递归的思想，层层递归直到终点，若发现希望得到的一条路径，则转储并打印输出；若发现环路，或发现死路，则停止寻路并返回；
3. 用栈保存当前已经寻到的路径（不是完整路径）上的节点，在每一次寻到完整路径时弹出栈顶节点；而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点，从而实现回溯。
实现代码
1.node.java
我要评论
import java.util.arraylist;
/* 表示一个节点以及和这个节点相连的所有节点 */
public class node
{
public string name = null;
public arraylist<node> relationnodes = new arraylist<node>();
public string getname() {
return name;
}
public void setname(string name) {
this.name = name;
}
public arraylist<node> getrelationnodes() {
return relationnodes;
}
public void setrelationnodes(arraylist<node> relationnodes) {
this.relationnodes = relationnodes;
}
}
2.test.java
import java.util.arraylist;
import java.util.iterator;
import java.util.stack;
public class test {
/* 临时保存路径节点的栈 */
public static stack<node> stack = new stack<node>();
/* 存储路径的集合 */
public static arraylist<object[]> sers = new arraylist<object[]>();
/* 判断节点是否在栈中 */
public static boolean isnodeinstack(node node)
{
iterator<node> it = stack.iterator();
while (it.hasnext()) {
node node1 = (node) it.next();
if (node == node1)
return true;
}
return false;
}
/* 此时栈中的节点组成一条所求路径，转储并打印输出 */
public static void showandsavepath()
{
object[] o = stack.toarray();
for (int i = 0; i < o.length; i++) {
node nnode = (node) o[i];
if(i < (o.length - 1))
system.out.print(nnode.getname() + "->");
else
system.out.print(nnode.getname());
}
sers.add(o); /* 转储 */
system.out.println("\n");
}
/*
* 寻找路径的方法
* cnode: 当前的起始节点currentnode
* pnode: 当前起始节点的上一节点previousnode
* snode: 最初的起始节点startnode
* enode: 终点endnode
*/
public static boolean getpaths(node cnode, node pnode, node snode, node enode) {
node nnode = null;
/* 如果符合条件判断说明出现环路，不能再顺着该路径继续寻路，返回false */
if (cnode != null && pnode != null && cnode == pnode)
return false;
if (cnode != null) {
int i = 0;
/* 起始节点入栈 */
stack.push(cnode);
/* 如果该起始节点就是终点，说明找到一条路径 */
if (cnode == enode)
{
/* 转储并打印输出该路径，返回true */
showandsavepath();
return true;
}
/* 如果不是,继续寻路 */
else
{
/*
* 从与当前起始节点cnode有连接关系的节点集中按顺序遍历得到一个节点
* 作为下一次递归寻路时的起始节点
*/
nnode = cnode.getrelationnodes().get(i);
while (nnode != null) {
/*
* 如果nnode是最初的起始节点或者nnode就是cnode的上一节点或者nnode已经在栈中 ，
* 说明产生环路 ，应重新在与当前起始节点有连接关系的节点集中寻找nnode
*/
if (pnode != null
&& (nnode == snode || nnode == pnode || isnodeinstack(nnode))) {
i++;
if (i >= cnode.getrelationnodes().size())
nnode = null;
else
nnode = cnode.getrelationnodes().get(i);
continue;
}
/* 以nnode为新的起始节点，当前起始节点cnode为上一节点，递归调用寻路方法 */
if (getpaths(nnode, cnode, snode, enode))/* 递归调用 */
{
/* 如果找到一条路径，则弹出栈顶节点 */
stack.pop();
}
/* 继续在与cnode有连接关系的节点集中测试nnode */
i++;
if (i >= cnode.getrelationnodes().size())
nnode = null;
else
nnode = cnode.getrelationnodes().get(i);
}
/*
* 当遍历完所有与cnode有连接关系的节点后，
* 说明在以cnode为起始节点到终点的路径已经全部找到
*/
stack.pop();
return false;
}
} else
return false;
}
public static void main(string[] args) {
/* 定义节点关系 */
int noderalation[][] =
{
{1}, //0
{0,5,2,3},//1
{1,4}, //2
{1,4}, //3
{2,3,5}, //4
{1,4} //5
};
/* 定义节点数组 */
node[] node = new node[noderalation.length];
for(int i=0;i<noderalation.length;i++)
{
node[i] = new node();
node[i].setname("node" + i);
}
/* 定义与节点相关联的节点集合 */
for(int i=0;i<noderalation.length;i++)
{
arraylist<node> list = new arraylist<node>();
for(int j=0;j<noderalation[i].length;j++)
{
list.add(node[noderalation[i][j]]);
}
node[i].setrelationnodes(list);
list = null; //释放内存
}
/* 开始搜索所有路径 */
getpaths(node[0], null, node[0], node[4]);
}
}
输出：
node0->node1->node5->node4
node0->node1->node2->node4
node0->node1->node3->node4
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问， 点击进行留言回复！！
详解SpringBoot修改启动端口server.port的四种方式
网友评论