查找有向圖中節點數最多的路徑

Question

在有向圖中查找節點數最多的路徑是一種好方法嗎？

我想我可以遍歷每個節點的深度圖，找出哪個路徑有最多的節點，但我想知道是否有更好的方法。

提及：圖形保證沒有周期。

Answer 1

您有一個有向無環圖（DAG），並且您想查找具有最大節點數的路徑。這實際上在DAG中找到了longest path。

這個問題在多項式時間內可以解決DAG。閱讀更多關於它在這裏： - Wikipedia.

Answer 2

如果圖有一個循環，那麼是「無限」長度的路徑。

如果圖是非循環的： 您應該運行拓撲排序。然後：

foreach(node in topological_sort_order) { 
    foreach(prev_node in neibhours[node]) { 
     // there is edge from prev_node to node 
     // since vertices are sorted in topological order than 
     // value for longest_path[prev_node] is already computed 
     longest_path[node] = max(longest_path[node], longest_path[prev_node] + 1); 
    } 
} 

Answer 3

由於您的輸入是有向圖，而不是向無環圖則是NP完全和提到的解決方案不起作用。但是，正如logic_max所說：這是最長的路徑問題，並且通過給每條邊設置一個成本來減少這個問題。