文章詳情頁
java - 如何求多叉樹兩個任意節(jié)點的最短路徑呢？
瀏覽：200日期：2024-02-02 11:31:00
問題描述
每個節(jié)點的數(shù)據(jù)結(jié)構(gòu)是一個value ，和這個節(jié)點的所有子節(jié)點
問題解答
回答1：設(shè)有n個節(jié)點。
樹轉(zhuǎn)無向圖，然后用n次dijkstra、spfa等單源最短路算法或1次floyd多源最短路算法求任意兩節(jié)點的值。但是當(dāng)n比較大的話儲存值對內(nèi)存的開銷較大。
使樹成為有根樹，每個節(jié)點i儲存到根的距離di。查詢兩節(jié)點di,dj時，求兩節(jié)點的公共祖先dk，則d(i,j)=di+dj-dk*2。關(guān)于公共祖先可以參考tarjan算法。
回答2：當(dāng)成無向圖考慮Floyd算法.
標(biāo)簽：
java
上一條：java - 一個類的對象鎖只有一個，類鎖呢？下一條：java - c++學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)不應(yīng)該用stl實現(xiàn)？
相關(guān)文章：
1. docker 下面創(chuàng)建的IMAGE 他們的 ID 一樣？這個是怎么回事？？？？2. 在應(yīng)用配置文件 app.php 中找不到’route_check_cache’配置項3. html按鍵開關(guān)如何提交我想需要的值到數(shù)據(jù)庫4. mysql取模分表與分表5. gvim - 誰有vim里CSS的Indent文件, 能縮進@media里面的6. HTML 5輸入框只能輸入漢字、字母、數(shù)字、標(biāo)點符號？正則如何寫？7. 跟著課件一模一樣的操作使用tp6,出現(xiàn)了錯誤8. PHP類屬性聲明？9. objective-c - ios 怎么實現(xiàn)微信聯(lián)系列表 最好是swift10. javascript - 請教如何獲取百度貼吧新增的兩個加密參數(shù)
排行榜
熱門標(biāo)簽
網(wǎng)公網(wǎng)安備