java如何实现查找无向连通图中两点间所有路径的算法
这篇文章主要为大家展示了“java如何实现查找无向连通图中两点间所有路径的算法”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java如何实现查找无向连通图中两点间所有路径的算法”这篇文章吧。
成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都网站建设、成都网站制作、忠县网络推广、微信小程序开发、忠县网络营销、忠县企业策划、忠县品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联为所有大学生创业者提供忠县建站搭建服务，24小时服务热线：028-86922220，官方网址：www.cdcxhl.com
算法要求：
1. 在一个无向连通图中求出两个给定点之间的所有路径；
2. 在所得路径上不能含有环路或重复的点；
算法思想描述：
1. 整理节点间的关系，为每个节点建立一个集合，该集合中保存所有与该节点直接相连的节点（不包括该节点自身）；
2. 定义两点一个为起始节点，另一个为终点，求解两者之间的所有路径的问题可以被分解为如下所述的子问题：对每一个与起始节点直接相连的节点，求解它到终点的所有路径（路径上不包括起始节点）得到一个路径集合，将这些路径集合相加就可以得到起始节点到终点的所有路径；依次类推就可以应用递归的思想，层层递归直到终点，若发现希望得到的一条路径，则转储并打印输出；若发现环路，或发现死路，则停止寻路并返回；
3. 用栈保存当前已经寻到的路径（不是完整路径）上的节点，在每一次寻到完整路径时弹出栈顶节点；而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点，从而实现回溯。
算法伪码(java描述)：
public Stack stack = new Stack();/*临时保存路径节点的栈*/
public ArrayList sers = new ArrayList();/*存储路径的集合*/
public class Node/*表示一个节点以及和这个节点相连的所有节点*/
{
public String name = null;
public ArrayList relationNodes = new ArrayList();
public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
public ArrayList getRelationNodes()
{
return relationNodes;
}
public void setRelationNodes(ArrayList relationNodes)
{
this.relationNodes = relationNodes;
}
}
public boolean isNodeInStack(Node node)/*判断节点是否在栈中*/
{
Iterator it = stack.iterator();
while(it.hasNext())
{
Node node1 = (Node)it.next();
if(node == node1)
return true;
}
return false;
}
public void showAndSavePath ()/*此时栈中的节点组成一条所求路径，转储并打印输出*/
{
Object[] o = stack.toArray();
for(int i = 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为起始节点到终点的路径已经全部找到*/
return false;
}
}
else
return false;
} 以上是“java如何实现查找无向连通图中两点间所有路径的算法”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
本文名称：java如何实现查找无向连通图中两点间所有路径的算法
链接地址：http://cdiso.cn/article/gpogji.html
