將無向圖轉化爲有約束的有向圖

給定無向圖和節點，如何將圖修改爲有向圖，使得任何路徑通向一個特定節點。問題將以在SE訪談中流行的算法問題將無向圖轉化爲有約束的有向圖

2013-02-03 user1938465

這只是創建一棵植根於（和指向）給定節點的樹，然後將其完成到DAG，任何搜索算法（例如BFS或DFS）都可以爲您提供解決方案：從給定節點開始，使用搜索算法 - 每遇到一個節點，將其連接到一個已經連接的節點（通常連接到您所連接的節點），然後可以根據順序設置剩餘邊的方向在其中你遇到了節點（從後者到耳朵）里爾）

來源

2013-02-03 19:25:14 Ofir

將無向圖轉化爲有約束的有向圖

回答

相關問題