Boost圖無向遍歷有向圖

Question

我正在使用Boost圖。我的圖的邊緣有一個直接的含義。那就是爲什麼我選擇了一個有向圖。但是當我遍歷圖時，我通常會忽略這個方向。然而，我還沒有找到一個解決方案來遍歷我的圖形，例如使用內置深度優先搜索。

有沒有解決方案，這不涉及複製整個圖形？

如果沒有：我不確定我的圖是否實際上是由自然導向的。也許我應該使用無向圖，並添加一些「方向」屬性？我不知道如何做到這一點（只要將源/目標vertex_descriptors附加到邊緣，顯然會在圖形發生變化時斷開）。有沒有可能做到這一點？它有意義嗎？

謝謝

Answer 1

我不知道Boost Graphs的實現，但我可以在你的案例中看到兩個選項。

1. 如果你的圖形不是很大，那麼你可以先創建一個非有向圖，然後計算你的「東西」，然後創建一個定向副本。這應該花費O(n)時間並且不會影響整體性能。
2. 使用非有向圖並添加一些關於邊的方向的信息，如指向源頂點的指針。這個解決方案可能會讓你的算法變得更加複雜一些，但是你可以避免任何數據拷貝，並在大圖上獲得一些性能。