文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：139日期：2024-02-02 11:31:00
问题描述
每个节点的数据结构是一个value ，和这个节点的所有子节点
问题解答
回答1：设有n个节点。
树转无向图，然后用n次dijkstra、spfa等单源最短路算法或1次floyd多源最短路算法求任意两节点的值。但是当n比较大的话储存值对内存的开销较大。
使树成为有根树，每个节点i储存到根的距离di。查询两节点di,dj时，求两节点的公共祖先dk，则d(i,j)=di+dj-dk*2。关于公共祖先可以参考tarjan算法。
回答2：当成无向图考虑Floyd算法.
标签：
java
相关文章：
1. mysql中的collate关键字是什么意思?2. python - django 按日归档统计订单求解3. javascript - jQuery中live事件在移动微信端下没有效果；代码如下4. python - django orm 过滤日期为当天日期的数据5. Android "1"=="1" 到底是true还是false6. android-studio - Android Studio 运行项目的时候一堆警告，跑步起来！？7. angular.js - 指令下的指令 面对上级指令ng-repeat的时候 ng-controller会出现多次的问题？8. css - 如何使用 vue transition 实现 ios 按钮一样的平滑切换效果9. javascript - 一个JS的算法，求大神解答10. 热切期待朱老师的回复，网页视频在线播放器插件配置错误
排行榜
网公网安备