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

本文实例为大家分享了java计算图两点之间的所有路径的具体代码,供大家参考,具体内容如下

1.给定图如下:

2.求0到3之间可达的所有路径

这里问题就是关于搜索遍历的问题,但其中需要注意到不能产生回路或环.

算法描述如下:

top_node:当前栈顶元素

adjvex_node;当前top_node已经访问的邻接点

next_node:即将访问的元素(top_node的第adjvex_node个邻接点所对应的元素)

找出所有路径采用的是遍历的方法,以“深度优先”算法为基础。从源点出发,先到源点的第一个邻接点N00,再到N00的第一个邻接点N10,再到N10的第一个邻接点N20...当遍历到目标点时表明找到一条路径。

上述代码的核心数据结构为一个栈,主要步骤:

①源点先入栈,并进行标记

②获取栈顶元素top_node,如果栈顶为终点时,即找到一条路径,栈顶元素top_node出栈,此时adjvex_node=top_node,新的栈顶元素为top_node,否则执行③

③从top_node的所有邻接点中,从adjvex_node为起点,选取下一个邻接点next_node;如果该元素非空,则入栈,使得adjvex_node=-1,(adjvex_node=-1代表top_node的邻接点一个还没有访问)做入栈标记。否则代表没有后续节点了,此时必须出栈栈顶元素,并置adjvex_node为该栈顶元素,并做出栈标记。

④为避免回路,已入栈元素要记录,选取新入栈顶点时应跳过已入栈的顶点,当栈为空时,遍历完成

3.java代码实现

1)图结构

点表

public class Vertex {
//存放点信息
public int data;
//与该点邻接的第一个边节点
public Edge firstEdge;
}

边表(代表与点相连的点的集合)

//边节点
public class Edge {
//对应的点下表
public int vertexId;
//边的权重
public int weight;
//下一个边节点
public Edge next;
//getter and setter自行补充
}

2).算法实现

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class graph {
public Vertex[] vertexList; //存放点的集合
public graph(int vertexNum){
 this.vertexNum=vertexNum;
 vertexList=new Vertex[vertexNum];
}
//点个数
public int vertexNum;
//边个数
public int edgeLength;
public void initVertext(int datas[]){
 for(int i=0;i<vertexNum;i++){
 Vertex vertext=new Vertex();
 vertext.data=datas[i];
 vertext.firstEdge=null;
 vertexList[i]=vertext;
 //System.out.println("i"+vertexList[i]);
 }
 isVisited=new boolean[vertexNum];
 for(int i=0;i<isVisited.length;i++){
 isVisited[i]=false;
 }
}
//针对x节点添加边节点y
public void addEdge(int x,int y,int weight){
 Edge edge=new Edge();
 edge.setVertexId(y);
 edge.setWeight(weight);
 //第一个边节点
 System.out.println(vertexList.length);
 if(null==vertexList[x].firstEdge){
 vertexList[x].firstEdge=edge;
 edge.setNext(null);
 }
 //不是第一个边节点,则采用头插法
 else{
 edge.next=vertexList[x].firstEdge;
 vertexList[x].firstEdge=edge;
 }
}
//得到x的邻接点为y的后一个邻接点位置,为-1说明没有找到
public int getNextNode(int x,int y){
 int next_node=-1;
 Edge edge=vertexList[x].firstEdge;
 if(null!=edge&&y==-1){
 int n=edge.vertexId;
 //元素还不在stack中
 if(!states.get(n))
  return n;
 return -1;
 }

 while(null!=edge){
 //节点未访问
 if(edge.vertexId==y){
  if(null!=edge.next){
   next_node=edge.next.vertexId;
  if(!states.get(next_node))
  return next_node;
  }
  else
  return -1;
 }
 edge=edge.next;
 }
 return -1;
}
//代表某节点是否在stack中,避免产生回路
public Map<Integer,Boolean> states=new HashMap();

//存放放入stack中的节点
public Stack<Integer> stack=new Stack();

//输出2个节点之间的输出路径
public void visit(int x,int y){
    //初始化所有节点在stack中的情况
    for(int i=0;i<vertexNum;i++){
 states.put(i,false);
 }
    //stack top元素
    int top_node;
 //存放当前top元素已经访问过的邻接点,若不存在则置-1,此时代表访问该top元素的第一个邻接点
    int adjvex_node=-1;
 int next_node;
 stack.add(x);
 states.put(x,true);
 while(!stack.isEmpty()){
 top_node=stack.peek();
 //找到需要访问的节点
        if(top_node==y){
  //打印该路径
  printPath();
  adjvex_node=stack.pop();
  states.put(adjvex_node,false);
 }
 else{
  //访问top_node的第advex_node个邻接点
            next_node=getNextNode(top_node,adjvex_node);
  if(next_node!=-1){
  stack.push(next_node);
  //置当前节点访问状态为已在stack中
                states.put(next_node,true);
  //临接点重置
                adjvex_node=-1;
  }
            //不存在临接点,将stack top元素退出
            else{
  //当前已经访问过了top_node的第adjvex_node邻接点
                adjvex_node=stack.pop();
  //不在stack中
  states.put(adjvex_node,false);
  }
 }
 }
}

//打印stack中信息,即路径信息
 public void printPath(){
 StringBuilder sb=new StringBuilder();
 for(Integer i :stack){
 sb.append(i+"->");
 }
 sb.delete(sb.length()-2,sb.length());
 System.out.println(sb.toString());
}

public static void main(String[]args){
 graph g=new graph(5);
 g.initVertext(new int[]{1,2,3,4,4});
 //System.out.println(g.vertexList[0]);
 g.addEdge(0,1,1);
 g.addEdge(0,2,3);
 g.addEdge(0,3,4);
 g.addEdge(1,2,1);
 g.addEdge(2,0,1);
 g.addEdge(2,3,1);
 g.addEdge(1,3,2);
 g.visit(0,3);
}
}

执行结果如下:

0->3
0->2->3
0->1->2->3

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

(0)

相关推荐

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

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

  • 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自带的Point类 import java.awt.Point;//引用awt包下的Point类,此类的功能是表示 (x,y) 坐标空间中的位置的点 public class Distance { public static void main(String[] args) { Point p1 = new Point(5, 6);// 定义第一个点的坐标(5,6) Point p2 = new Point(7,8);// 定义第二个点的坐标(7,8) //定位坐标 System.o

  • Java与Python之间使用jython工具类实现数据交互

    最近有个功能需要java与python之间的数据交互,java需要把参数传给python,然后python计算的结果返回给java.于是就写了一个工具类. 首先,maven 需要加载jython的依赖.工具类代码如下: import java.util.List; import java.util.Map; import java.util.Properties; import org.apache.poi.ss.formula.functions.T; import org.python.co

  • js实现两点之间画线的方法

    本文实例讲述了js实现两点之间画线的方法.分享给大家供大家参考.具体分析如下: 最近有点无聊,琢磨了很久,想到了一消磨时间的点子,也就是做js版的连连看. 两点之间画线也只是连连看最基本功能的一部分,所以我画的线也仅是折线,而且还只能向左折,后面将根据连连看中图片位置点来确定折线的方向. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/

  • 浅谈Java工程读取resources中资源文件路径的问题

    正常在Java工程中读取某路径下的文件时,可以采用绝对路径和相对路径,绝对路径没什么好说的,相对路径,即相对于当前类的路径.在本地工程和服务器中读取文件的方式有所不同,以下图配置文件为例. 本地读取资源文件 java类中需要读取properties中的配置文件,可以采用文件(File)方式进行读取: File file = new File("src/main/resources/properties/basecom.properties"); InputStream in = new

  • java获取日期之间天数的方法

    本文实例讲述了java获取日期之间天数的方法.分享给大家供大家参考.具体实现方法如下: private int daysBetween(Date now, Date returnDate) { Calendar cNow = Calendar.getInstance(); Calendar cReturnDate = Calendar.getInstance(); cNow.setTime(now); cReturnDate.setTime(returnDate); setTimeToMidni

  • 根据经纬度计算地球上两点之间的距离js实现代码

    利用JS实现的根据经纬度计算地球上两点之间的距离 最近用到了根据经纬度计算地球表面两点间距离的公式,然后就用JS实现了一下. 计算地球表面两点间的距离大概有两种办法. 第一种是默认地球是一个光滑的球面,然后计算任意两点间的距离,这个距离叫做大圆距离(The Great Circle Distance). 公式如下: 使用JS来实现为: 复制代码 代码如下: var EARTH_RADIUS = 6378137.0; //单位M var PI = Math.PI; function getRad(

  • Python求两点之间的直线距离(2种实现方法)

    方法一: #导入math包 import math #定义点的函数 class Point: def __init__(self,x=0,y=0): self.x=x self.y=y def getx(self): return self.x def gety(self): return self.y #定义直线函数 class Getlen: def __init__(self,p1,p2): self.x=p1.getx()-p2.getx() self.y=p1.gety()-p2.ge

随机推荐