java查找无向连通图中两点间所有路径的算法
之前就这个问题发帖求教过,过了几天没看到回复就没再关心。后来自己设计了一个算法,在公司的项目中实践了一下,效果还可以,贴出来供大家参考。
算法要求:
1. 在一个无向连通图中求出两个给定点之间的所有路径;
2. 在所得路径上不能含有环路或重复的点;
算法思想描述:
1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身);
2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一个与起始节点直接相连的节点,求解它到终点的所有路径(路径上不包括起始节点)得到一个路径集合,将这些路径集合相加就可以得到起始节点到终点的所有路径;依次类推就可以应用递归的思想,层层递归直到终点,若发现希望得到的一条路径,则转储并打印输出;若发现环路,或发现死路,则停止寻路并返回;
3. 用栈保存当前已经寻到的路径(不是完整路径)上的节点,在每一次寻到完整路径时弹出栈顶节点;而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点,从而实现回溯。
算法伪码(java描述):
publicStackstack=newStack();/*临时保存路径节点的栈*/ publicArrayListsers=newArrayList();/*存储路径的集合*/ publicclassNode/*表示一个节点以及和这个节点相连的所有节点*/ { publicStringname=null; publicArrayListrelationNodes=newArrayList(); publicStringgetName() { returnname; } publicvoidsetName(Stringname) { this.name=name; } publicArrayListgetRelationNodes() { returnrelationNodes; } publicvoidsetRelationNodes(ArrayListrelationNodes) { this.relationNodes=relationNodes; } } publicbooleanisNodeInStack(Nodenode)/*判断节点是否在栈中*/ { Iteratorit=stack.iterator(); while(it.hasNext()) { Nodenode1=(Node)it.next(); if(node==node1) returntrue; } returnfalse; } publicvoidshowAndSavePath()/*此时栈中的节点组成一条所求路径,转储并打印输出*/ { Object[]o=stack.toArray(); for(inti=0;i=cNode.getRelationNodes().size()) nNode=null; else nNode=cNode.getRelationNodes().get(i); continue; } /*以nNode为新的起始节点,当前起始节点cNode为上一节点,递归调用寻路方法*/ if(getPaths(nNode,cNode,sNode,eNode))/*递归调用*/ { stack.pop();/*如果找到一条路径,则弹出栈顶节点*/ } i++;/*继续在与cNode有连接关系的节点集中测试nNode*/ if(i>=cNode.getRelationNodes().size()) nNode=null; else nNode=cNode.getRelationNodes().get(i); } stack.pop();/*当遍历完所有与cNode有连接关系的节点后,说明在以cNode为起始节点到终点的路径已经全部找到*/ returnfalse; } } else returnfalse; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。