简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
java - 如何求多叉树两个任意节点的最短路径呢？
ringa_lee
ringa_lee 2017-04-18 10:48:59
0
2
596

每个节点的数据结构是一个value ，和这个节点的所有子节点

ringa_lee
ringa_lee

ringa_lee

全部回复(2)
Ty80
Ty802017-04-18 10:50:59 2 楼

设有n个节点。

  1. 树转无向图，然后用n次dijkstra、spfa等单源最短路算法或1次floyd多源最短路算法求任意两节点的值。但是当n比较大的话储存值对内存的开销较大。

  2. 使树成为有根树，每个节点i储存到根的距离di。查询两节点di,dj时，求两节点的公共祖先dk，则d(i,j)=di+dj-dk*2。关于公共祖先可以参考tarjan算法。

点赞 +0
添加回复
小葫芦
小葫芦2017-04-18 10:50:59 1 楼

当成无向图考虑Floyd算法.

点赞 +0
添加回复
热门专题
更多>
热门文章
热门教程
更多>
相关教程
热门推荐
最新课程
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网：公益在线PHP培训，帮助PHP学习者快速成长！