java搜索无向图中两点之间所有路径的算法
作者:lijiao 发布时间:2023-11-10 09:28:26
标签:java,无向图,路径
参考 java查找无向连通图中两点间所有路径的算法,对代码进行了部分修改,并编写了测试用例。
算法要求:
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
来源:https://blog.csdn.net/hcx25909/article/details/8043107
0
投稿
猜你喜欢
- 一:需求当小数位很多的时候,小数位后面可能有一些多余的0并没有任何实际意义。所以在某些业务需求下可以去掉这些多余的0。例如:0.2000可以
- yml 文件规则yml文件的好处,天然的树状结构,一目了然,实质上跟properties是差不多的。不支持tab缩进可以使用 "-
- 注册BeanPostProcessorrefresh()调用registerBeanPostProcessors(beanFactory)方
- 公司的老项目要改造多租户,于是进入了大坑,本文写点遇到的坑以及解决方案,每次遇到问题在网上搜了好久,记录下来,防止以后忘掉。(一).方案网上
- LinkedListLinkedList是一种可以在任何位置进行高效地插入和删除操作的有序序列。它的最基本存储结构是一个节点:每个节点将存储
- java常量池技术java中常量池技术说的通俗点就是java级别的缓存技术,方便快捷的创建一个对象。当需要一个对象时,从池中去获取(如果池中
- RabbitMQ的示例,涉及到Direct、Fanout、Topic和Headers交换机以及普通队列、延迟队列和死信队列在pom.xml文
- 通过 SpringBoot 实现了表单下的文件上传,前后端分离情况下的文件上传。本案例不连接数据库,只做基本的文件上传操作。在 Spring
- 前言服务消费者调用服务提供者的时候使用RestTemplate技术存在不便之处:拼接urlrestTmplate.getForObJect这
- servlet实现文件上传,预览,下载和删除,供大家参考,具体内容如下一、准备工作:1.1 文件上传插件:uploadify;1.2 文件上
- Java 利用poi把数据库中数据导入Excel效果:使用时先把poi包导入工程的path,注意只需要导入poi包即可,下载后有三个jar包
- 前言关于mybatis-plus的简介以及基本使用,我在《SpringBoot整合mybatis-plus–入门超详细》一文中已做介绍,此处
- mybatis 查询返回Map<String,Object> 类型,平时没太注意怎么用,今天又遇到了总结记录一下,方便以后处理此
- @Transactional是我们在用Spring时候几乎逃不掉的一个注解,该注解主要用来声明事务。它的实现原理是通过Spring AOP在
- 问题在使用 Abp 框架的后台作业时,当后台作业抛出异常,会导致整个程序崩溃。在 Abp 框架的底层执行后台作业的时候,有 try/catc
- 在定位JVM性能问题时可能会遇到内存泄露导致JVM OutOfMemory的情况,在使用Tomcat容器时如果设置了reloadable=”
- ArrayList和LinkedList都实现了List接口,有以下的不同点:1、ArrayList是基于索引的数据接口,它的底层是数组。它
- Class.forName(xxx.xx.xx) 返回的是一个类一.首先你要明白在java里面任何class都要装载在虚拟机上才能运行。1.
- 具体可见http://developer.android.com/tools/debugging/ddms.html。 DDMS为IDE和e
- 在分布式系统中,配置文件散落在每个项目中,难于集中管理,抑或修改了配置需要重启才能生效。下面我们使用 Spring Cloud Config