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

java中怎么计算图两点之间的所有路径？针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

兴安网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作，到程序开发，运营维护。创新互联成立于2013年到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

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 states=new HashMap();
 
//存放放入stack中的节点
public Stack stack=new Stack();
 
//输出2个节点之间的输出路径
public void visit(int x,int y){
    //初始化所有节点在stack中的情况
    for(int i=0;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 

关于java中怎么计算图两点之间的所有路径问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注创新互联行业资讯频道了解更多相关知识。

分享文章：java中怎么计算图两点之间的所有路径
网站URL：http://shouzuofang.com/article/iedgoj.html