構建并描述一個有效的演算法，該演算法將兩個有向無環圖 (DAG) 作為輸入，并找到出現在這兩個有向無環圖 (DAG) 中的最長路徑。
如果有幾個，演算法應該回傳最長的路徑之一（哪一個無關緊要）。總之，給定圖 G = (V,E) 和 G' =(V',E')，找到最長的可能序列 <v1,...,vk> 其中 (v_i,v_{i 1})對于 i = 1...k-1，在 E和E' 中。
有任何想法嗎？我可以自己撰寫實際代碼，我只需要幫助構建實際演算法背后的想法并找到問題的解決方案。
我想我可以使用遞回 DFS 和一些記憶：同時跟蹤訪問過的節點；對于每個起始節點和每個鄰居，計算到鄰居的距離 從鄰居到目標的距離。然后取其中的最大值，將其記為該節點的最大值，然后回傳。
對兩個 DAG 使用這種方法，這里的問題是確定這些路徑中的哪一條是兩者中出現的最長路徑。
將不勝感激任何想法/幫助。
uj5u.com熱心網友回復：
兩種做法：
從每個頂點開始，找出最長的公共路徑是什么。DFS 記憶。回傳最大長度。如果您還想要路徑，請記住最長的路徑。
找到 DAG 的交集并回傳最長的相交路徑。您可以在
在第一種方法中，您找出最大匹配路徑的長度（此處為 BCD）并回傳長度。
在第二種方法中，您將存盤匹配的部分（此處為 BCD）并從中回傳最長的路徑長度。
方法三：
@"n. 1.8e9-where's-my-share m。" 在評論中提到了另一種方法，您可以從一個圖中洗掉另一個圖中不存在的邊。
因此，如果您從圖 1 中洗掉圖 2 中不存在的邊，您將得到以下結果：
在上圖中，如果你做 DFS，你會得到 3 作為答案，因為 BCD 是最長的路徑。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/380761.html上一篇：帶回傳值的樹遍歷函式