Prim最小生成樹

在圖論中，最小生成樹（Minimum Spanning Tree, MST）是一個連通圖的子圖，包含所有頂點，且邊的權值總和最小。Prim算法是一種用來找到加權圖的最小生成樹的算法。

Prim算法的基本思想是從圖中隨意選擇一個頂點作為起點，然後逐步添加邊，每次都選擇權值最小的邊將未被包含在最小生成樹中的頂點連接到最小生成樹中。

以下是Prim算法的步驟：

1. 隨機選擇一個頂點作為起點，並將其標記為已訪問。
2. 構造一個包含起點的圖的子圖，這個子圖就是最小生成樹的初始狀態。
3. 從未被訪問的鄰居頂點中選擇一個與已訪問頂點之間邊的權值最小的頂點，將其標記為已訪問，並將該邊添加到最小生成樹中。
4. 重複步驟3，直到所有頂點都被訪問過。

以下是一個簡單的Python實現：

from collections import deque

def prim(graph):
    # graph是無向加權圖的表示，可以是字典或 adjacency list
    visited = [False] * len(graph)
    min_spanning_tree = []
    start = 0  # 起點索引

    # 初始化起點為已訪問
    visited[start] = True
    min_spanning_tree.append((start, graph[start][start]))

    while len(min_spanning_tree) < len(graph):
        # 找到未被訪問的頂點中與最小生成樹連接的邊的權值最小的頂點
        min_weight = float('inf')
        min_index = -1
        for i in range(len(graph)):
            if not visited[i] and (min_weight > graph[start][i]):
                min_weight = graph[start][i]
                min_index = i

        # 如果找不到這樣的頂點，則算法結束
        if min_index == -1:
            break

        # 標記頂點為已訪問，並將邊添加到最小生成樹中
        visited[min_index] = True
        min_spanning_tree.append((min_index, min_weight))

    return min_spanning_tree

# 示例圖
graph = {
    0: {1: 6, 2: 4},
    1: {0: 6, 2: 5},
    2: {0: 4, 1: 5}
}

# 運行算法
min_spanning_tree = prim(graph)

# 輸出最小生成樹
for v, weight in min_spanning_tree:
    print(f"({v}, weight={weight})")

這個算法會找到給定圖的最小生成樹，並將其作為一個頂點和邊的列表返回。請注意，這個算法假設圖是連通的，如果圖不連通，則算法可能會掛起或返回不正確的結果。