從給定邊緣構建DAG

讓我們繪製N個沒有邊緣的垂直圖。從給定邊緣構建DAG

讓我們邊的名單：

x1 y1 
x2 y2 
x3 y3 
. 
. 
. 
xk yk

我們必須從1處理所有邊緣到k。我們不得不說，如果第x個邊緣正在循環圖。如果不是，請將其添加到圖表中。

如何有效地做到這一點？我的意思是不要檢查DFS是否第x個邊緣每次都製作循環圖。

有什麼更快的？這是波蘭SPOJ問題

https://pl.spoj.pl/problems/XIWTPZF/

感謝您的任何幫助。 Chris

來源

2011-05-31 Spinach

創建一個邊緣對象。在邊緣對象中你有兩個標誌。跟蹤標誌和添加的標誌。從要檢查的邊緣列表中構建您的對象模型。添加所有邊，並連接使用邊對象中的指針進行鏈接的邊。向模型添加邊時，鏈接到新添加的邊以及以新添加的邊的起點爲終點的所有先前添加的邊。

當您測試邊緣時，首先將其設置爲臨時添加標誌。然後遞歸跟蹤，隨時設置跟蹤標誌。如果碰撞已經有跡象的邊緣，則返回false，並在出路中清除跟蹤標誌。重要的部分是，你不追蹤沒有設置添加標誌的邊緣。

如果不發生碰撞，則在沒有觸及跟蹤標誌的情況下，對於終止的每條邊都返回true。

如果返回true，則移動到您的有序列表中的下一條邊。如果返回false，請清除添加的標誌。

在跟蹤結束時，檢查添加的標誌。

在這個位置（所以不要糾正我的C++語法）嚴重的僞代碼：http://pastebin.com/dT2bFmqp

來源

2011-05-31 21:56:33

這通過去除實際添加的低效和刪除對象模型的邊緣可以節省一些時間，這就需要去耦和刪除對象。此外，您還可以獲得訂單檢查清單以及對象模型，因此最後只需循環檢查訂單檢查清單即可。此時，您可以移除未添加的項目，並且您有最終的列表。如果您在檢測階段使用接口並在使用階段使用單獨的接口，那麼您不必爲使用階段保留較大的接口。 – 2011-05-31 22:09:51

一般來說，我不確定這樣做的有效方法。我認爲你可以通過將你的圖分成不相交的集合來獲得一些效率，但是這取決於你的具體輸入圖的佈局，這將取決於你獲得多少收益。另外，你可以採取其他一些快捷方式（比如檢查你連接的邊是否有邊），但是這又取決於你的特定圖的屬性是否對你有幫助。

這是我想出的算法可能是效率不高，只要你願意：

# No cycles on an empty list 
for edge in edgeList: 
    graph.addEdge(edge) 
    cycles = detectCycle(graph) 
    if cycles 
     graph.removeEdge(edge)

來源

2011-05-31 21:42:59

從給定邊緣構建DAG

回答

相關問題