當前位置：首頁 > 编程语言 > python >内容正文

python

Python小白的数学建模课-18.最小生成树问题

發布時間：2025/3/15 python 35 豆豆

生活随笔收集整理的這篇文章主要介紹了 Python小白的数学建模课-18.最小生成树问题小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

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

最小生成樹（MST）是圖論中的基本問題，具有廣泛的實際應用，在數學建模中也經常出現。
路線設計、道路規劃、官網布局、公交路線、網絡設計，都可以轉化為最小生成樹問題，如要求總線路長度最短、材料最少、成本最低、耗時最小。
最小生成樹的典型算法有普里姆算法（Prim算法）和克魯斯卡算法（Kruskal算法）。
本文基于 NetworkX 工具包，通過例程詳細介紹最小生成樹問題的求解。
『Python小白的數學建模課 @ Youcans』帶你從數模小白成為國賽達人。

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 的最小/最大生成樹函數

函數功能

minimum_spanning_tree(G[, weight,…])	計算無向圖上的最小生成樹
maximum_spanning_tree(G[, weight,…])	計算無向圖上的最大生成樹
minimum_spanning_edges(G[, algorithm,…])	計算無向加權圖最小生成樹的邊
maximum_spanning_edges(G[, algorithm,…])	計算無向加權圖最大生成樹的邊

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() 的返回值是最小生成樹的構成邊，類型為<class ‘generator’>，需要用 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≥10n\geq10$ ，由鍵盤輸入；
（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 np import 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 = 20 np.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])) # 向節點添加位置屬性 posposCity.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 axis plt.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})]

歡迎關注『Python小白的數學建模課 @ Youcans』原創作品

原創作品，轉載必須標注原文鏈接：(https://blog.csdn.net/youcans/article/details/118566422)。

Crated：2021-07-12

歡迎關注『Python小白的數學建模課 @ Youcans』系列，持續更新
Python小白的數學建模課-01.新手必讀
Python小白的數學建模課-02.數據導入
Python小白的數學建模課-03.線性規劃
Python小白的數學建模課-04.整數規劃
Python小白的數學建模課-05.0-1規劃
Python小白的數學建模課-06.固定費用問題
Python小白的數學建模課-07.選址問題
Python小白的數學建模課-09.微分方程模型
Python小白的數學建模課-10.微分方程邊值問題
Python小白的數學建模課-12.非線性規劃
Python小白的數學建模課-15.圖論的基本概念
Python小白的數學建模課-16.最短路徑算法
Python小白的數學建模課-17.條件最短路徑算法
Python小白的數學建模課-18.最小生成樹問題
Python小白的數學建模課-19.網絡流優化問題
Python小白的數學建模課-20.網絡流優化案例
Python小白的數學建模課-21.關鍵路徑法
Python小白的數學建模課-A1.國賽賽題類型分析
Python小白的數學建模課-21.關鍵路徑法
Python小白的數學建模課-22.插值方法
Python小白的數學建模課-A1.國賽賽題類型分析
Python小白的數學建模課-A2.2021年數維杯C題探討
Python小白的數學建模課-A3.12個新冠疫情數模競賽賽題及短評
Python小白的數學建模課-B2. 新冠疫情 SI模型
Python小白的數學建模課-B3. 新冠疫情 SIS模型
Python小白的數學建模課-B4. 新冠疫情 SIR模型
Python小白的數學建模課-B5. 新冠疫情 SEIR模型
Python小白的數學建模課-B6. 新冠疫情 SEIR改進模型

總結

以上是生活随笔為你收集整理的Python小白的数学建模课-18.最小生成树问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： ue4 android vulkan,在
下一篇： python入门基础篇（三）序列切片，列