最小生成樹之普利姆（prim）算法的python實作

普裡姆算法（Prim算法），圖論中的一種算法，可在權重連通圖裡搜尋得到最小生成樹。最小生成樹即在一個帶權連通圖中，不但包括了連通圖裡的所有頂點，且其所有邊的權值之和亦為最小。

算法思路

利用字典建立圖

以字典的形式建立權重連通圖，通常以各頂點為字典的鍵，與該頂點所能連通的其餘頂點再次構成一個子字典。這個子字典的鍵為所能連通的頂點，值為這個有向邊的權重。這個子字典則構成了一個完整的值。

例如以下權重連通圖：

可表示為：

graph = {

            0: {1: 4, 7: 8},

            1: {2: 8, 7: 11},

            2: {8: 2, 5: 4, 3: 7},

            3: {4: 9, 5: 14},

            4: {5: 10},

            5: {6: 2},

            6: {7: 1, 8: 6},

            7: {8: 7}

        }           

将所有邊放入同一個清單中

将所有邊以三元組（始點，終點，權值）的形式放入一個清單中。

def init_edges(graph):

    edges = []

    for i in graph.keys():

        for j in graph[i].keys():

            edges.append((i,j,graph[i][j]))

return edges

           

前期準備

随機選擇一個頂點加入到seen清單中，用來表示已經遇到過的頂點。

choice表示建構最小生成樹時所有被選上的邊，初始為空清單。

seen_edge表示所有已經碰到過的邊，prim主要對這個清單進行處理，初始時為空清單。

主體循環部分

1. 判斷已遇到過的頂點數量和總頂點數量的關系，當已遇到過的頂點數量少于總頂點數量時，說明還沒有成功構造出含所有頂點的最小生成樹，于是進入循環。
2. 每次循環都會将剛剛遇到過的頂點所能連接配接的邊全部加入到seen_edge清單中，然後将seen_edge按權重進行由大到小的排序。
3. 如果seen_edge中權值最小的邊的終點不在seen清單中，則将該終點加入到seen清單中，同時将這個邊加入到choice清單中，随後将該邊從seen_edge清單中删除，然後回到第1步。如果seen_edge中權值最小的邊的終點已經在seen清單中，則不再考慮這條邊，删除并繼續找此時seen_edge中權值最小的邊。
4. 步驟一無法進行下去後，傳回的choice清單即為建構出最小生成樹所需要的全部邊。

graph = {
            0: {1: 4, 7: 8},
            1: {2: 8, 7: 11},
            2: {8: 2, 5: 4, 3: 7},
            3: {4: 9, 5: 14},
            4: {5: 10},
            5: {6: 2},
            6: {7: 1, 8: 6},
            7: {8: 7}
        }

def init_edges(graph):
    edges = []
    for i in graph.keys():
        for j in graph[i].keys():
            edges.append((i,j,graph[i][j]))
    return edges

def prim(graph):
    seen = [list(graph.keys())[0]]
    choice = []
    edges = init_edges(graph)
    seen_edge = []
    
    while len(seen) <= len(graph.keys()):
        for i in edges:
            if i[0] == seen[-1]:
                seen_edge.append(i)
        seen_edge.sort(key = lambda x:x[-1],reverse = True)
        while 1:
            if seen_edge[-1][1] not in seen:
                seen.append(seen_edge[-1][1])
                choice.append(seen_edge.pop())
                break
            else:
                seen_edge.pop()
        
                
        
    return choice

choice = prim(graph)