Python小白的數學建模課-18.最小生成樹問題

最小生成樹（MST）是圖論中的基本問題，具有廣泛的實際應用，在數學建模中也經常出現。

路線設計、道路規劃、官網布局、公交路線、網路設計，都可以轉化為最小生成樹問題，如要求匯流排路長度最短、材料最少、成本最低、耗時最小。

最小生成樹的典型演算法有普里姆演算法（Prim演算法）和克魯斯卡演算法（Kruskal演算法）。

本文基於 NetworkX 工具包，透過例程詳細介紹最小生成樹問題的求解。

1。最小生成樹

1。1 生成樹

樹是圖論中的基本概念。連通的無圈圖稱為樹（Tree），就是不包含迴圈的迴路的連通圖。

對於無向連通圖，如下圖所示，生成樹（Spanning tree）是原圖的極小連通子圖，它包含原圖中的所有 n 個頂點，並且有保持圖連通的最少的邊，即只有足以構成一棵樹的 n-1 條邊。

生成樹滿足：（1）包含連通圖中所有的頂點；（2）任意兩頂點之間有且僅有一條通路。因此，生成樹中邊的數量 = 頂點數 - 1。

對於非連通無向圖，遍歷每個連通分量中的頂點集合所經過的邊是多顆生成樹，這些連通分量的生成樹構成非連通圖的生成森林。

1。2 最小生成樹和最大生成樹

遍歷連通圖的方式通常有很多種，也就是說一張連通圖可能有多種不同的生成樹。

無向賦權圖的生成樹中，各條邊的權重之和最小的生成樹，稱為最小生成樹（minimum spanning tree，MST），也稱最小權重生成樹。

對應地，各條邊的權重之和最大的生成樹，稱為最大生成樹（maximum spanning tree）。

1。3 最小生成樹問題

最小生成樹（MST）是圖論中的基本問題，具有廣泛的實際應用，在數學建模中也經常出現。

例如，在若干城市之間鋪設通訊線路，使任意兩個城市之間都可以通訊，要使鋪設線路的總費用最低，就需要找到最小生成樹。類似地，路線設計、道路規劃、官網布局、公交路線、網路設計，都可以轉化為最小生成樹問題，如要求匯流排路長度最短、材料最少、成本最低、耗時最小等。

在實際應用中，不僅要考慮網路連通，還要考慮連通網路的質量和效率，就形成了帶有約束條件的最小生成樹：

直徑限制最小生成樹（Bounded diameter minimum spanning tree）：對給定的連通圖，滿足直徑限制的生成樹中，具有最小權的樹，稱為直徑限制最小生成樹。直徑限制最小生成樹問題在資源最佳化問題中應用廣泛，如網路設計的網路直徑影響到網路的傳輸速度、效率和能耗。

度限制最小生成樹（Degree constrained minimum spanning tree）：對給定的連通圖，滿足某個節點或全部節點的度約束（如入度不超過 k）的生成樹中，具有最小權的樹，稱為度限制最小生成樹。實際應用中，為了控制節點故障對整個系統的影響，需要對節點的度進行限制。

2。最小生成樹演算法

構造最小生成樹的演算法很多，通常是從空樹開始，按照貪心法逐步選擇並加入 n-1 條安全邊（不產生迴路），最終得到最小生成樹。

最小生成樹的典型演算法有普里姆演算法（Prim演算法）和克魯斯卡演算法（Kruskal演算法）。

2。1 普里姆演算法（Prim演算法）

Prim 演算法以頂點為基礎構造最小生成樹，每個頂點只與連通圖連線一次，因此不用考慮在加入頂點的過程中是否會形成迴路。

演算法從某一個頂點 s 開始，每次選擇剩餘的代價最小的邊所對應的頂點，加入到最小生成樹的頂點集合中，逐步擴充直到包含整個連通網的所有頂點，可以稱為“加點法”。

Prim 演算法中圖的存貯結構採用鄰接矩陣，使用一個頂點集合 u 構造最小生成樹。由於不斷向集合u中加點，還需要建立一個輔助陣列來同步更新最小代價邊的資訊。

Prim 演算法每次選擇頂點時，都需要進行排序，但每次都只需要對一部分邊進行排序。Prim 演算法的時間複雜度為 O（n*n），與邊的數量無關，適用於邊很多的稠密圖。

採用堆實現優先佇列來維護最小點，可以將Prim演算法的時間複雜度降低到 O（mlogn），稱為Prim_heap 演算法，但該演算法的空間消耗很大。

2。2 克魯斯卡演算法（Kruskal演算法）

Kruskal 演算法以邊為基礎構造最小生成樹，利用避圈思想，每次找到不使圖構成迴路的代價最小的邊。

演算法初始邊數為 0，每次選擇一條滿足條件的最小代價邊，加入到邊集合中，逐步擴充直到包含整個生成樹，可以稱為“加邊法”。

Kruskal 演算法中圖的存貯結構採用邊集陣列，權值相等的邊在陣列中的排列次序是任意的。Kruskal演算法開始就要對所有的邊進行排序，之後還需要對所有邊應用 Union-Find演算法，但不再需要排序。

Kruskal 演算法的時間複雜度為 O（mlogm），主要是對邊排序的時間複雜度，適用於邊較少的稀疏圖。

3。 NetworkX 的最小生成樹演算法

3。1 NetworkX 的最小/最大生成樹函式

3。2 minimum_spanning_tree（）使用說明

minimum_spanning_tree(G, weight=‘weight’, algorithm=‘kruskal’, ignore_nan=False)

minimum_spanning_edges(G, algorithm=‘kruskal’, weight=‘weight’, keys=True, data=True, ignore_nan=False)

minimum_spanning_tree（）用於計算無向連通圖的最小生成樹（森林）。minimum_spanning_edges（）用於計算無向連通圖的最小生成樹（森林）的邊。

對於連通無向圖，計算最小生成樹；對於非連通無向圖，計算最小生成森林。

主要引數：

G（undirected graph）：無向圖。

weight（str）：指定用作計算權重的邊屬性。

algorithm（string）：計算最小生成樹的演算法，可選項為 ‘kruskal’、‘prim’ 或 ‘boruvka’。預設演算法為 ‘kruskal’。

data（bool）：指定返回值是否包括邊的權值。

ignore_nan（bool）：在邊的權重為 Nan 時產生異常。

返回值：

minimum_spanning_tree（）的返回值是由最小生成樹構成的圖，型別為 NetworkX Graph，需要用 T。edges（）獲得對應的最小生成樹的邊。

minimum_spanning_edges（）的返回值是最小生成樹的構成邊，型別為，需要用 list（）轉換為列表資料。

3。3 案例：天然氣管道鋪設問題

問題描述：

某市區有 7個小區需要鋪設天然氣管道，各小區的位置及可能的管道路線、費用如圖所示，要求設計一個管道鋪設路線，使天然氣能輸送到各個小區，且鋪設管道的總費用最小。

程式說明：

這是一個最小生成樹問題，用 NetworkX 的 minimum_spanning_tree（）函式即可求出費用最小的管道路線。

圖的輸入。本例為稀疏的有權無向圖，使用 G。add_weighted_edges_from（）函式以列表向圖中新增多條賦權邊，每個賦權邊以元組（node1，node2，weight）表示。

nx。minimum_spanning_tree（）和 nx。tree。minimum_spanning_edges（）都可以計算最小生成樹，引數設定和屬性也基本一致，區別主要在於返回值的格式和呼叫方式。

Python 例程：

程式執行結果：

［1， 2， 3， 4， 5， 6， 7， 8］［（1， 2），（1， 3），（2， 4），（4， 7），（4， 5），（5， 8），（6， 7）］［（1， 2），（1， 3），（2， 4），（4， 5），（4， 7），（5， 8），（6， 7）］［（1， 2， {‘weight’： 5}），（1， 3， {‘weight’： 6}），（2， 4， {‘weight’： 2}），（4， 5， {‘weight’： 8}），（4， 7， {‘weight’： 4}），（5， 8， {‘weight’： 1}），（6， 7， {‘weight’： 5}）］［（5， 8， {‘weight’： 1}），（2， 4， {‘weight’： 2}），（4， 7， {‘weight’： 4}），（1， 2， {‘weight’： 5}），（6， 7， {‘weight’： 5}），（1， 3， {‘weight’： 6}），（4， 5， {‘weight’： 8}）］［（1， 2），（2， 4），（4， 7），（7， 6），（1， 3），（4， 5），（5， 8）］

4。案例：建設通訊網路

4。1 問題描述

在 n 個城市架設 n-1 條線路，建設通訊網路。任意兩個城市之間都可以建設通訊線路，且單位長度的建設成本相同。求建設通訊網路的最低成本的線路方案。

（1）城市數 n ≥ 10 n\geq10n≥10，由鍵盤輸入；

（2）城市座標 x， y 在（0～100）之間隨機生成；

（3）輸出線路方案的各段線路及長度。

4。1 程式說明

這是一個典型的最小生成樹問題。n 個城市構成圖的 n 個頂點，任意兩個頂點之間都有連線邊，邊的權值是兩個頂點的間距。

輸入。

本例程對應案例中的各項約束條件：必須經過圖中的綠色節點；必須經過圖中的兩段綠色路段；必須避開圖中的紅色路段；儘可能以最少的花費到達終點。

本例程是一個遍歷簡單路徑、判斷約束條件的通用框架。

all（n in path for n in （2，4，7，12，13，14））的作用，一是判斷路徑中是否包括必經點 N7、N12；二是判斷路徑中是否包括必經邊（2，4）、（13，14）的各頂點，這不僅可以減小計算量，而且能確保下面使用 index（）查詢頂點位置時不會發生錯誤。

4。2 Python 例程

# mathmodel18_v1。py# Demo18 of mathematical modeling algorithm# Demo of minimum spanning tree（MST） with NetworkX# Copyright 2021 YouCans， XUPT# Crated：2021-07-10import numpy as npimport matplotlib。pyplot as plt # 匯入 Matplotlib 工具包import networkx as nx # 匯入 NetworkX 工具包from scipy。spatial。distance import pdist， squareform# # 2。城市通訊網路建設# nCities = input（“Input number of cities （n>=10）：”）# nCities = int（nCities）nCities = 20np。random。seed（1）xPos = np。random。randint（0， 100， nCities） # 生成［0，100）均勻分佈的隨機整數yPos = np。random。randint（0， 100， nCities） # 生成 Ncities 個城市座標posCity = ［］G2 = nx。complete_graph（nCities） # 建立：全連線圖for node in G2。nodes（）： G2。add_node（node， pos=（xPos［node］， yPos［node］）） # 向節點新增位置屬性 pos posCity。append（G2。nodes［node］［“pos”］） # 獲取節點位置屬性 posdist = squareform（pdist（np。array（posCity））） # 計算所有節點之間的距離for u， v in G2。edges： G2。add_edge（u， v， weight=np。round（dist［u］［v］，decimals=1）） # 向邊新增權值 dist（u，v）T = nx。minimum_spanning_tree（G2， algorithm=‘kruskal’） # 返回包括最小生成樹的圖print（“\n城市位置：\n”，G2。_node）print（“\n通訊網路：\n”，sorted（T。edges（data=True））） # data=True 表示返回值包括邊的權重# mst = nx。tree。minimum_spanning_edges（G2， algorithm=“kruskal”） # 返回最小生成樹的邊# for edge in sorted（list（mst））：# print（edge）fig， ax = plt。subplots（figsize=（8， 6））node_pos = nx。get_node_attributes（G2， ‘pos’） # 頂點位置nx。draw（G2，node_pos，with_labels=True，node_color=‘c’，edge_color=‘silver’，node_size=300，font_size=10，font_color=‘r’，alpha=0。8） # 繪製無向圖# nx。draw_networkx_labels（G2， node_pos， labels=node_pos， font_size=6， horizontalalignment=‘left’， verticalalignment=‘top’） # 繪製頂點屬性：位置座標 pos# edge_col = ［‘red’ if edge in T。edges（） else ‘silver’ for edge in G2。edges（）］ # 設定邊的顏色# nx。draw_networkx_edges（G2， node_pos， edge_color=edge_col， width=2） # 設定指定邊的顏色nx。draw_networkx_edges（G2， node_pos， edgelist=T。edges， edge_color=‘r’， width=2） # 設定指定邊的顏色edge_weight = nx。get_edge_attributes（T， ‘weight’） # 邊的權值nx。draw_networkx_edge_labels（T， node_pos， edge_labels=edge_weight， font_size=8， font_color=‘m’， verticalalignment=‘top’） # 顯示邊的權值plt。axis（‘on’） # Remove the axisplt。xlim（-5， 100）plt。ylim（-5， 100）plt。show（）

4。3 執行結果

城市位置： {0： {‘pos’：（37， 29）}， 1： {‘pos’：（12， 14）}， 2： {‘pos’：（72， 50）}， 3： {‘pos’：（9， 68）}， 4： {‘pos’：（75， 87）}， 5： {‘pos’：（5， 87）}， 6： {‘pos’：（79， 94）}， 7： {‘pos’：（64， 96）}， 8： {‘pos’：（16， 86）}， 9： {‘pos’：（1， 13）}， 10： {‘pos’：（76， 9）}， 11： {‘pos’：（71， 7）}， 12： {‘pos’：（6， 63）}， 13： {‘pos’：（25， 61）}， 14： {‘pos’：（50， 22）}， 15： {‘pos’：（20， 57）}， 16： {‘pos’：（18， 1）}， 17： {‘pos’：（84， 0）}， 18： {‘pos’：（11， 60）}， 19： {‘pos’：（28， 81）}}通訊網路：［（0， 1， {‘weight’： 29。2}），（0， 14， {‘weight’： 14。8}），（0， 15， {‘weight’： 32。8}），（1， 9， {‘weight’： 11。0}），（1， 16， {‘weight’： 14。3}），（2， 4， {‘weight’： 37。1}），（2， 14， {‘weight’： 35。6}），（3， 8， {‘weight’： 19。3}），（3， 12， {‘weight’： 5。8}），（4， 6， {‘weight’： 8。1}），（4， 7， {‘weight’： 14。2}），（5， 8， {‘weight’： 11。0}），（8， 19， {‘weight’： 13。0}），（10， 11， {‘weight’： 5。4}），（10， 17， {‘weight’： 12。0}），（11， 14， {‘weight’： 25。8}），（12， 18， {‘weight’： 5。8}），（13， 15， {‘weight’： 6。4}），（15， 18， {‘weight’： 9。5}）］