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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • java查找无向连通图中两点间所有路径的算法

    之前就这个问题发帖求教过,过了几天没看到回复就没再关心.后来自己设计了一个算法,在公司的项目中实践了一下,效果还可以,贴出来供大家参考. 算法要求: 1. 在一个无向连通图中求出两个给定点之间的所有路径: 2. 在所得路径上不能含有环路或重复的点: 算法思想描述: 1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身): 2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一个与起始节点直接

  • java查找图中两点之间所有路径

    本文实例为大家分享了java查找图中两点之间所有路径的具体代码,基于邻接表,供大家参考,具体内容如下 图类: package graph1; import java.util.LinkedList; import graph.Graph.edgeNode; public class Graph { class EdgeNode{ int adjvex; EdgeNode nextEdge; } class VexNode{ int data; EdgeNode firstEdge; boolea

  • java计算图两点之间的所有路径

    本文实例为大家分享了java计算图两点之间的所有路径的具体代码,供大家参考,具体内容如下 1.给定图如下: 2.求0到3之间可达的所有路径 这里问题就是关于搜索遍历的问题,但其中需要注意到不能产生回路或环. 算法描述如下: top_node:当前栈顶元素 adjvex_node;当前top_node已经访问的邻接点 next_node:即将访问的元素(top_node的第adjvex_node个邻接点所对应的元素) 找出所有路径采用的是遍历的方法,以"深度优先"算法为基础.从源点出发,

  • java搜索无向图中两点之间所有路径的算法

    参考 java查找无向连通图中两点间所有路径的算法,对代码进行了部分修改,并编写了测试用例. 算法要求: 1. 在一个无向连通图中求出两个给定点之间的所有路径: 2. 在所得路径上不能含有环路或重复的点: 算法思想描述: 1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身): 2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一 个与起始节点直接相连的节点,求解它到终点的所有路径(路径上

  • Java求10到100000之间的水仙花数算法示例

    本文实例讲述了Java求10到100000之间的水仙花数算法.分享给大家供大家参考,具体如下: 水仙花数: 概念:水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身.(例如:1^3 + 5^3+ 3^3 = 153) 算法思路分析:这个算法我们分两个步骤来进行:第一:我们做一个求一个数的位数的函数:第二:我们通过调用此函数来进行10到100000之间素数的计算! 下面给出具体的代码(仅供参考): package javastudy; public class

  • Java web开发中加载图片路径的两种方式

    (1)   src="/image/1_it.jpg" (2)   src="http://localhost:8080/image/1_it.jpg" 其中localhost可以换位你的电脑IP,端口号也要相应改变. 以上均在基于编译器idea以及tomcat服务器开发的web中测试可行!都是要先定位到项目的位置! 以上所述是小编给大家介绍的Java web开发加载图片路径的两种方式,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

  • Java实现计算图中两个顶点的所有路径

    目录 前言 抽象数据模型 代码实现数据模型 计算两个顶点之间路径算法 总结 前言 最近公司的项目上有个需求,还挺有分享价值的,这边做个记录.需求大致如下,下面的一个流程图,点击条件线上选择的内容,必须是前面配置过的节点,如果不是,需要在保存的时候做强校验提示. 需求其实很明确,抽象出来就是获取图中两个顶点之间所有可达路径的顶点集合,大家可以思考下,该如何实现?这里面涉及到了数据结构中图相关知识,而数据结构算法也是本事最大的弱项,还是废了我一番工夫. 抽象数据模型 实际上,看到这个需求就很容易想到

  • Java修改eclipse中web项目的server部署路径问题

    和MyEclipse不一样,在Eclipse中做的Web项目默认是不支持将项目发布到Web服务器上的,会发布到工作空间的某个目录,因此无法在外部启动Tomcat来运行Web项目,只有打开Eclipse中的服务器,才能运行Web项目.所以要对Eclipse进行修改,才能将做好的项目,发布到Tomcat服务器上,发布到服务器上的Webapps文件夹下. 在Eclipse中,默认会把Web项目放到Eclipse的工作空间下的.metadata\.plugins\org.eclipse.wst.serv

  • Java实现无向图的示例详解

    目录 基本概念 图的定义 无向图的定义 无向图的 API 无向图的实现方式 邻接矩阵 边的数组 邻接表数组 无向图的遍历 深度优先搜索 广度优先搜索 后记 基本概念 图的定义 一个图是由点集V={vi} 和 VV 中元素的无序对的一个集合E={ek} 所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素 ek叫做边. 对于V中的两个点 u,v,如果边(u,v) 属于E,则称 u,v两点相邻,u,v称为边(u,v)的端点. 我们可以用m(G)=|E| 表示图G中的边数,用n(G)

  • 深入解读Java代码组织中的package包结构

    如果我们在Class对象上调用getPackage方法,就可以得到描述该类所在包的Package对象(Package类是在java.lang中定义的).我们也可以用包名通过调用静态方法getPackage或者调用静态方法getPackages(该方法返回由系统中所有已知包构成的数组)来获得Package对象.getName方法可以返回包的全名. Package对象的使用与其他反射类型完全不同,即我们不能在运行时创建或操纵包.我们可以使用Package对象来获取有关包的信息,诸如包的用途.谁创建了

随机推荐