没有合适的资源?快使用搜索试试~ 我知道了~
java计算图两点之间的所有路径
13 下载量 71 浏览量
2020-08-26
10:20:51
上传
评论
收藏 69KB PDF 举报
温馨提示
试读
3页
主要为大家详细介绍了java计算图两点之间的所有路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
资源推荐
资源详情
资源评论
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;
资源评论
weixin_38661939
- 粉丝: 5
- 资源: 950
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功