文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：125日期：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. python - 子进程执行完成为僵尸进程，怎么解决2. javascript - 初学angularJS+express，路由路径中/转换成%2F，导致路径失效，求原因？3. javascript - vue2.0动态加载多个相同组件，给组件中的data输入不同的值，关闭非最后一个组件时，销毁的值是最后一个组件值。4. 【python小白】 问关于导入嵌套的包的问题5. android - rxjava buffer操作符使用6. javascript - nodejs关于进程间发送句柄的一点疑问7. MySQL部署单机多实例无法初始化数据库8. html5 - 百度Ueditor代码高亮和代码段滚动条冲突是怎么回事?9. javascript - QQ第三方登录的问题10. mysql - SQL 这个 left jion 和 left outer jion 怎么结果是一样的?
排行榜
网公网安备