文章詳情頁
java - 如何求多叉樹兩個任意節點的最短路徑呢？
瀏覽：138日期：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. java - 如何在Fragment中調用Activity的onNewIntent?2. python - （初學者）代碼運行不起來，求指導，謝謝！3. python的文件讀寫問題？4. mysql里的大表用mycat做水平拆分，是不是要先手動分好，再配置mycat5. javascript - jquery hide()方法無效6. javascript - js 對中文進行MD5加密和python結果不一樣。7. javascript - 圖片鏈接請求一直是pending狀態，導致頁面崩潰，怎么解決？8. window下mysql中文亂碼怎么解決？？9. python - 獲取到的數據生成新的mysql表10. javascript - h5上的手機號默認沒有識別
排行榜
網公網安備