java计算图两点之间的所有路径 - CSDN文库

java计算两点之间所有路径

java计算图两点间所有路径

java计算两点间路径

29 浏览量更新于2023-03-16 评论收藏 69KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

主要为大家详细介绍了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;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

weixin_38661939

粉丝: 5
资源: 950

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈