有趣的圖(四)(58)
小朋友們好，大朋友們好！
我是貓妹，一名愛上Python編程的小學生。
和貓妹學Python，一起趣味學編程。
今日主題
之前學過了圖的基本概念和圖的兩種遍歷算法
怎么樣？
你學會了嗎？
接下來，咱們學習下幾種圖的應用。
今天，咱們要學習的內容是：
什么是樹
圖的最小生成樹算法
圖和樹
圖，之前咱們已經學習過了。
在計算機中，什么是樹呢？
樹是圖的子集，樹是圖，圖不一定是樹。
樹是一種“層次”關系，圖是“網絡”關系。
樹是一種特殊的圖：
1. 一個無環(huán)的無向連通圖，稱之為樹。
2. 由n個點、n-1條邊組成的無向連通圖，稱之為樹。
證明：
n個點要連通，至少需要n-1條邊（無向邊），而剛好n-1條邊必然不能構成環(huán)（要構成環(huán)，至少有一個點的度數≥3），所以這是一棵樹。
圖可以有環(huán)，樹沒有環(huán)。
我們直觀感受下：
圖是兩個集合 V 和 E 的集合，其中 V 是頂點的有限非空集，E 是邊的有限非空集。?
頂點只不過是圖中的節(jié)點。?
兩個相鄰的頂點由邊連接。?
任何圖都表示為 G = {V, E}。?
示例：G = {{V1, V2, V3, V4, V5, V6}, {E1, E2, E3, E4, E5, E6, E7}}
樹是一個或多個節(jié)點的有限集合，使得：?
有一個專門指定的節(jié)點，稱為 root。?
其余節(jié)點被劃分為 n>=0 不相交集 T1, T2, T3, …, Tn?
其中 T1, T2, T3, …, Tn 稱為根的子樹。
12
圖的最小生成樹算法
最小生成樹算法是用來求解一個圖的最小生成樹的算法。
比如，下圖中的圖產生了兩個數，下左的權重和是15，下右的權重和是16。
所謂圖的最小生成樹，就是找到一棵樹，其權重和最小。
常用的最小生成樹算法有 Kruskal 算法和 Prim 算法。
Kruskal 算法的思想，簡單來說，就是如果一個圖有 n 個頂點，選出總權值最小并且不會構成回路的 n-1 條邊使得圖中的任意兩個頂點都能通過這 n-1 條邊中的若干條邊連通。
對于 Kruskal 算法的實現，既然要選擇選擇 n-1 條邊并且邊的總權值最小，那么我們可以先對這個圖的所有邊按權值進行從小到大排序，然后依次選擇邊。
Prim 算法是一種貪心算法，用于在加權連通圖中找到其最小生成樹。
具體來說，我們從一個未被包含在最小生成樹中的點開始，每次選擇距離該點最近的未被包含在最小生成樹中的點，并將它們連接起來形成一條邊。
這樣一直進行下去，直到所有的點都被包含在最小生成樹中為止。
Prim 算法實現
邏輯很簡單，先選取一個起始節(jié)點，然后從其相鄰的邊種，選取權值最小的邊進行連接。
將新連接后的節(jié)點和之前的節(jié)點一起，從這些節(jié)點中選取權值最小的邊進行連接。
如此反復。知道所有的節(jié)點都被訪問。
比如：
和0連接的邊中，權值分別為{10、28}，選取10。
加入節(jié)點5，和節(jié)點{0,5}相鄰的邊有{25,28}，選取25。
如此反復。
從幾個權值中，選取一個最小的。
這個要怎么實現呢？
可以用Python中的heapq實現。
heapq庫提供了一些函數，如heappush、heappop、heappushpop等，用于操作堆。
代碼實現（完整代碼，見同名公眾號，次條推文）：
代碼邏輯：
14行：s表示已經訪問過的結點
15行：優(yōu)先級隊列，用于找一個最小權值
16行：res，實際生成的最小生成樹路徑
17行：邊的數量比結點少一
18~19行：將當前結點相鄰結點和權值放入隊列
22行：從隊列中選擇一個權值最小的
23行：結點不能訪問過，否則就不是樹了
24行：保存當前結點
25行：保存當前路徑
26行：更新當前結點
運行結果：
好了，我們今天就學到這里吧！
如果遇到什么問題，咱們多多交流，共同解決。
我是貓妹，咱們下次見！
