[Java] 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;
 }
}

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