隨機化最小割

Vibe Prompt

「實作 Karger's Contraction 演算法，找到圖形的最小割。跑 100 次取最佳結果。」

import random, copy

def karger_min_cut(graph):
    """
    graph: {node: [neighbors]}
    """
    while len(graph) > 2:
        # 隨機選一條邊
        u = random.choice(list(graph.keys()))
        v = random.choice(graph[u])
        
        # 合併 v 到 u
        graph[u].extend(graph[v])
        for w in graph[v]:
            graph[w] = [u if x == v else x for x in graph[w]]
        graph[u] = [x for x in graph[u] if x != u]
        del graph[v]
    
    # 剩餘兩節點之間的邊數 = 最小割
    nodes = list(graph.keys())
    return len([x for x in graph[nodes[0]] if x == nodes[1]])

def find_min_cut(graph, trials=100):
    best = float('inf')
    for i in range(trials):
        g = copy.deepcopy(graph)
        cut = karger_min_cut(g)
        if cut < best:
            best = cut
            print(f"第 {i+1} 次: 找到更小割 {best}")
    return best

# 測試
graph = {
    0: [1, 2, 3],
    1: [0, 2, 3],
    2: [0, 1, 3, 4],
    3: [0, 1, 2, 4],
    4: [2, 3, 5, 6],
    5: [4, 6],
    6: [4, 5],
}

min_cut = find_min_cut(graph, trials=50)
print(f"最小割: {min_cut}")

# 理論值：這個圖的最小割是 2（切開 {4,5,6}）

本章總結

• 理解核心概念與原理
• 掌握實作方法與技巧
• 熟悉常見問題與解決方案
• 能夠應用於實際專案

延伸閱讀

• 官方文件與 API 參考
• GitHub 開源專案範例
• 相關技術書籍與課程
• 社群討論與技術部落格

實作範例

基礎範例

# 本節提供一個完整的實作範例
# 讓你能夠將所學應用到實際專案中

步驟說明

1. 初始化：設定開發環境與必要工具
2. 資料準備：收集與整理所需資料
3. 核心實作：實作主要功能與邏輯
4. 測試驗證：確保功能正確運作
5. 最佳化：調整效能與使用者體驗

常見錯誤

| 錯誤類型 | 可能原因 | 解決方法 | |---------|---------|---------| | 編譯錯誤 | 語法問題 | 檢查程式碼語法 | | 執行錯誤 | 環境問題 | 確認相依套件已安裝 | | 邏輯錯誤 | 演算法問題 | 逐步除錯與測試 | | 效能問題 | 效率問題 | 使用效能分析工具 |

程式碼範例

# 範例程式碼
import sys

def main():
    # 主程式邏輯
    print("Hello, World!")

if __name__ == "__main__":
    main()

相關資源

• 官方文件
• API 參考手冊
• 開源專案範例
• 技術社群討論