我想要查找DAG中兩個節點之間的路徑數。 O(V^2)和O(V + E)是可接受的。 O(V + E)提醒我以某種方式使用BFS或DFS,但我不知道如何使用BFS或DFS,但我不知道如何使用BFS或DFS。 有人可以幫忙嗎?DAG中兩個節點之間的路徑數
10
A
回答
17
做一個拓撲排序的DAG,然後將目標的頂點向後掃描到源。對於每個頂點v
,保留從v
到目標的路徑數量。當你到達源頭時,計數值就是答案。那是O(V+E)
。
6
從節點u到v的不同路徑的數量是從節點x到v的不同路徑的總和,其中x是u的直接後裔。
存儲每個節點(臨時設置爲0)的目標節點v的路徑數量,使用相反方向從v(此處值爲1)開始,併爲每個節點重新計算此值(將所有子節點的值)直到你到達你。
如果按拓撲順序處理節點(又是相反的方向),則可以保證在訪問給定節點時已經計算了所有直接後代。
希望它有幫助。
相關問題
- 1. 如何查找DAG中兩個頂點之間的最大權重路徑?
- 2. 兩個圖形節點之間的固定長度路徑
- 3. Neo4j - 如何找到兩個節點之間的最短路徑
- 4. 誘導子圖;兩個節點之間的路徑存在
- 5. 找到任意兩個節點之間最長的路徑
- 6. 查找兩個節點之間的所有路徑
- 7. 計算DAG中通過節點的最短路徑數
- 8. 繪製兩點之間的路徑
- 9. 兩點之間最長的路徑
- 10. 如何找到兩個節點之間的循環圖中最長的路徑?
- 11. 基於不同條件的圖中兩個節點之間的最短路徑
- 12. 獲取兩個節點之間的路徑並使用它來匹配兩個其他類型的節點
- 13. 要找到兩個給定節點/頂點之間的最大路徑
- 14. 查找無向圖中兩個節點之間的所有可能路徑
- 15. 如何找到Lisp中兩個節點之間最長的路徑?
- 16. 找到Tinkerpop中兩個節點之間最短路徑的最佳方法3.1
- 17. 未加權圖/樹中兩個給定節點之間的最短路徑
- 18. 使用BFS和DFS查找圖表中兩個節點之間的路徑
- 19. Django發現圖中兩個頂點之間的路徑
- 20. 如何計算Android中兩個地圖點之間的路徑?
- 21. 平衡二叉樹中兩個節點之間的最短路徑如何受到路徑「權重」的影響?
- 22. 兩個表之間的依賴路徑
- 23. 從源節點上查找DAG上的最長路徑
- 24. 跨多個矩陣的節點之間的最短路徑
- 25. 使用BFS的2個節點之間的路徑
- 26. neo4j - 找到兩個以上節點之間的所有最短路徑
- 27. C#圖遍歷 - 任意兩個節點之間的跟蹤路徑
- 28. 使用BFS算法獲取兩個節點之間的最短路徑
- 29. DAG最短路徑
- 30. 在鏈表中插入兩個節點之間的節點
這是功課嗎? – 2011-03-02 07:57:52
這應該轉向理論 – 2013-03-28 18:13:50