檢測邊緣是否是在一個週期內最重的邊緣

Question

如此看來，在確定邊緣是否處於最小生成樹可以降低到的邊緣是否是一些週期的最重的邊緣問題。我知道如何使用DFS檢測邊緣是否處於循環中，但是如何確定它是否是該循環中最重的邊緣？是通過找到週期並選擇最重的邊緣嗎？

Answer 1

假設所有的邊緣有不同的權重，簡單和優雅的公平算法，這樣做是做一個修改DFS。請注意，如果此邊緣在某個循環中是最重的邊緣，那麼如果要查看通過刪除比當前邊緣重的所有邊緣形成的圖形，則必須存在從邊緣端點返回到邊緣，因爲這條路徑與邊緣本身相結合形成一個循環，給定的邊緣是最重的邊緣。相反，如果沒有包含給定邊緣最重的邊的循環，那麼如果您要在該圖中從邊緣回到源搜索，您將無法返回到邊緣的來源，否則你可以完成它的一個循環。這提供了以下簡單的算法：在原始圖形中從邊緣端點返回到源，但是每當遇到比原始邊緣更重的邊緣時，請不要處理它（這會模擬將其從圖）。如果你的DFS從邊緣回到源頭，那麼你知道必須有一些循環的邊緣是最重的邊緣，如果沒有這樣的循環，那麼你將無法獲得回到邊緣的源頭。

在邊緣沒有明顯的情況下，你會做同樣的搜索同上，但你會刪除其重量大於或等於當前邊的權重所有邊緣。其原因是，如果在這個變換圖中存在從邊的末端到邊的開始的路徑，則知道事實上我們並沒有最終使用具有與原始邊緣，因此找到的任何路徑都可以完成到給定邊緣最重的週期。如果沒有路徑，則要麼

1. 包含給定邊的每個週期有一些邊緣的嚴格比它更重，或
2. 包含給定邊的每個週期有一定的優勢，具有相同的成本，因爲它。

在這兩種情況下，它不是在循環中最重的邊緣。

該算法的運行時間爲O（M + N），做一個標準DFS所需的時間。

希望這會有所幫助！