本站精选了一篇java算法相关的编程文章，网友宰水桃根据主题投稿了本篇教程内容，涉及到java、两点之间路径、代码、java计算图两点之间的路径总结相关内容，已被917网友关注，下面的电子资料对本篇知识点有更加详尽的解释。
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).算法实现
public class Vertex {
//存放点信息
public int data;
//与该点邻接的第一个边节点
public Edge firstEdge;
}</pre>
</div>
<p>
边表(代表与点相连的点的集合)</p>
<div class="my516code">
<pre class="brush:java;">
//边节点
public class Edge {
//对应的点下表
public int vertexId;
//边的权重
public int weight;
//下一个边节点
public Edge next;
//getter and setter自行补充
}</pre>
</div>
<p>
2).算法实现</p>
<div class="my516code">
<pre class="brush:java;">
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;
}
}
