考慮一個具有N個頂點的任意連接（非回圈/回圈）無向 圖，頂點編號從1到N。每個頂點都有一些分配給它的值。讓值由A1, A2, A3, ... AN表示，其中A[i]表示第 i 個頂點的值。令P是A的一個排列。每次操作，我們可以交換兩個相鄰頂點的值。是否有可能實作A = P，即在所有1 <= i <= N的所有交換操作A[i] = P[i]之后。換句話說，每個頂點i應該在操作后具有值P[i]。PS - 我對在哪里問這個感到困惑 - 堆疊溢位或 math.stack 交換。提前道歉。
編輯1：我認為答案應該是肯定的。但我只是在對5個頂點的不同型別圖的案例分析的基礎上這么說。我嘗試將排列修改為 Q，其中 Q1 < Q2 < .. 這稍微改變了一個問題，現在最終狀態應該是 A1 < A2 < A3 ... AN。那么可以說圖可以排序了嗎？如果我的假設是錯誤的，請糾正我。
uj5u.com熱心網友回復：
確實這是可能的。由于我們有一個連通圖，我們可以洗掉邊，直到你得到一棵樹。洗掉一條邊僅僅意味著在這種情況下我們不會使用它來進行相鄰交換。“洗掉節點”僅僅意味著我們永遠不會交換節點的值。
現在我們可以使用以下演算法來產生排列：
- 選擇一個葉子并確定排列后打算位于那里的值的位置。反復將值與葉子路徑上的下一個值交換，直到該值到達葉子為止。
- 從樹上取下葉子；結果圖仍然是一棵樹
- 繼續 1.，如果還有任何節點。
在每次迭代中，我們通過執行一系列交換來將圖的大小減少 1，這些交換可以從上面以節點數量為界，因此通過有限數量的交換，我們能夠產生前突變。該演算法可能無法使用最佳交換次數產生解決方案，但它表明它可以完成。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/424813.html
上一篇：為什么這個使用余弦的數值方程會在控制臺應用程式和Windows應用程式之間產生不同的結果？
下一篇：Python，小數和