Python: Prim Algorithms and Kruskal Algorithms-北京尧图网络

项目结构本文展示了一个珠宝供应链物流规划的Python实现采用领域驱动设计(DDD)架构包含Prim和Kruskal两种最小生成树算法。系统主要包含领域模型LogisticsNode(实体)、LogisticsEdge(值对象)、LogisticsMST(聚合根)核心算法PrimAlgorithm(稠密图)、KruskalAlgorithm(稀疏图)应用服务层协调领域对象和算法示例演示了从缅甸矿区到各地门店的最低成本运输路线规划系统特点严格遵循DDD分层架构算法服务封装在领域层支持邻接矩阵(Prim)和边列表(Kruskal)两种输入输出格式化路线详情和总成本适用于珠宝等贵重物品的高效物流网络规划。# encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:14 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : AggregateRoot.py class AggregateRoot: 聚合根父类DDD聚合根顶层抽象 def __init__(self): self._domain_events [] def get_domain_events(self): :return: return self._domain_events.copy() def clear_domain_events(self): :return: self._domain_events.clear() # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:36 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : Entity.py class Entity: 实体父类拥有唯一业务ID def __init__(self, node_id: int): self._id node_id property def id(self) - int: return self._id def __eq__(self, other): if not isinstance(other, Entity): return False return self.id other.id # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:36 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : ValueObject.py class ValueObject: 值对象父类不可变基于属性判等 def __eq__(self, other): if not isinstance(other, ValueObject): return False return self.__dict__ other.__dict__ def __hash__(self): return hash(tuple(sorted(self.__dict__.items()))) # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:38 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : DomainException.py class DomainException(Exception): 领域统一业务异常 def __init__(self, message: str): self.message message super().__init__(self.message) # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:38 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : UnionFind.py class UnionFind: 并查集基础设施Kruskal算法专用路径压缩普通合并 def __init__(self, size: int): self.parent list(range(size)) def find(self, x: int) - int: 查找根节点路径压缩 :param x: :return: if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) - bool: 合并两个集合 :return: True合并成功无环False同集合成环 root_x self.find(x) root_y self.find(y) if root_x root_y: return False self.parent[root_y] root_x return True # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:40 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : LogisticsNode.py from PrimKruskal.Common.Entity import Entity class LogisticsNode(Entity): 物流网点【实体】代表珠宝供应链节点矿区、加工厂、仓库、线下门店 def __init__(self, node_id: int, node_name: str, node_category: str): super().__init__(node_id) self._node_name node_name self._node_category node_category property def node_name(self) - str: return self._node_name property def node_category(self) - str: return self._node_category def __repr__(self): return fNode id{self.id}, name{self.node_name}, type{self.node_category} # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:41 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : LogisticsEdge.py from PrimKruskal.Common.ValueObject import ValueObject class LogisticsEdge(ValueObject): 物流运输线路【值对象】两个网点之间运输链路权重运输综合成本押运、损耗、路费、保险不可变排序、判等基于起点、终点、成本 def __init__(self, start_id: int, end_id: int, cost: float): self.start_id start_id self.end_id end_id self.cost cost def __repr__(self): return fEdge {self.start_id}-{self.end_id}, cost{self.cost} # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:41 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : LogisticsMST.py from PrimKruskal.Common.AggregateRoot import AggregateRoot from PrimKruskal.Domain.Model.LogisticsEdge import LogisticsEdge from PrimKruskal.Domain.Model.LogisticsNode import LogisticsNode from typing import List class LogisticsMST(AggregateRoot): 最小生成树【聚合根】聚合包含全部网点、MST选中线路、总成本封装领域结果统一对外输出结构化数据 def __init__(self): super().__init__() self.all_nodes: List[LogisticsNode] [] self.mst_edges: List[LogisticsEdge] [] self.total_cost: float 0.0 def set_nodes(self, nodes: List[LogisticsNode]): self.all_nodes nodes def set_mst_result(self, edges: List[LogisticsEdge], total_cost: float): self.mst_edges edges self.total_cost total_cost def get_edge_detail(self) - List[tuple]: 格式化线路详情用于打印展示 node_map {node.id: node.node_name for node in self.all_nodes} detail_list [] for edge in self.mst_edges: s_name node_map[edge.start_id] e_name node_map[edge.end_id] detail_list.append((s_name, e_name, edge.cost)) return detail_list # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:42 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : PrimAlgorithm.py from PrimKruskal.Common.DomainException import DomainException from PrimKruskal.Domain.Model.LogisticsEdge import LogisticsEdge from PrimKruskal.Domain.Model.LogisticsNode import LogisticsNode from typing import List class PrimAlgorithm: 领域算法服务Prim最小生成树适用场景珠宝密集网点加工厂、门店扎堆稠密图入参邻接矩阵、节点集合出参MST线路列表、总成本 staticmethod def calculate(adj_matrix: List[List[float]], nodes: List[LogisticsNode]) - (List[LogisticsEdge], float): node_count len(nodes) if node_count 0: raise DomainException(网点集合不能为空无法生成物流路网) INF float(inf) in_mst [False] * node_count min_dist [INF] * node_count pre_node [-1] * node_count min_dist[0] 0 total_cost 0.0 mst_edge_list [] for _ in range(node_count): # 选取距离生成树最近节点 select_idx -1 min_val INF for i in range(node_count): if not in_mst[i] and min_dist[i] min_val: min_val min_dist[i] select_idx i if select_idx -1: raise DomainException(当前网点图不连通无法构建完整物流最小生成树) in_mst[select_idx] True total_cost min_val # 记录前驱边 pre_idx pre_node[select_idx] if pre_idx ! -1: edge LogisticsEdge(pre_idx, select_idx, adj_matrix[pre_idx][select_idx]) mst_edge_list.append(edge) # 松弛更新邻接点距离 for j in range(node_count): weight adj_matrix[select_idx][j] if not in_mst[j] and weight 0 and weight min_dist[j]: min_dist[j] weight pre_node[j] select_idx return mst_edge_list, total_cost # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:43 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : KruskalAlgorithm.py from PrimKruskal.Common.UnionFind import UnionFind from PrimKruskal.Common.DomainException import DomainException from PrimKruskal.Domain.Model.LogisticsEdge import LogisticsEdge from PrimKruskal.Domain.Model.LogisticsNode import LogisticsNode from typing import List class KruskalAlgorithm: 领域算法服务Kruskal最小生成树适用场景珠宝跨城分散门店、矿区稀疏图节点多直达线路少 staticmethod def calculate(edge_list: List[LogisticsEdge], nodes: List[LogisticsNode]) - (List[LogisticsEdge], float): node_count len(nodes) if node_count 0: raise DomainException(网点集合不能为空无法生成物流路网) # 边按成本升序排序 sorted_edges sorted(edge_list, keylambda e: e.cost) uf UnionFind(node_count) mst_edge_list [] total_cost 0.0 for edge in sorted_edges: if uf.union(edge.start_id, edge.end_id): mst_edge_list.append(edge) total_cost edge.cost if len(mst_edge_list) node_count - 1: break if len(mst_edge_list) ! node_count - 1: raise DomainException(当前网点图不连通无法构建完整物流最小生成树) return mst_edge_list, total_cost # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:44 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : LogisticsRouteService.py from PrimKruskal.Domain.Algorithm.PrimAlgorithm import PrimAlgorithm from PrimKruskal.Domain.Algorithm.KruskalAlgorithm import KruskalAlgorithm from PrimKruskal.Domain.Model.LogisticsMST import LogisticsMST from PrimKruskal.Domain.Model.LogisticsNode import LogisticsNode from PrimKruskal.Domain.Model.LogisticsEdge import LogisticsEdge from typing import List class LogisticsRouteApplicationService: 应用服务珠宝物流路线规划应用用例职责组装领域数据、调用领域算法、组装聚合根、对外提供统一业务接口不写业务逻辑只做协调编排 staticmethod def build_mst_by_prim(adj_matrix: List[List[float]], nodes: List[LogisticsNode]) - LogisticsMST: 使用Prim算法生成物流最小生成树 edges, cost PrimAlgorithm.calculate(adj_matrix, nodes) mst LogisticsMST() mst.set_nodes(nodes) mst.set_mst_result(edges, cost) return mst staticmethod def build_mst_by_kruskal(edge_list: List[LogisticsEdge], nodes: List[LogisticsNode]) - LogisticsMST: 使用Kruskal算法生成物流最小生成树 edges, cost KruskalAlgorithm.calculate(edge_list, nodes) mst LogisticsMST() mst.set_nodes(nodes) mst.set_mst_result(edges, cost) return mst调用# encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 22:44 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : PrimKruskalBll.py from PrimKruskal.Application.LogisticsRouteService import LogisticsRouteApplicationService from PrimKruskal.Domain.Model.LogisticsNode import LogisticsNode from PrimKruskal.Domain.Model.LogisticsEdge import LogisticsEdge class PrimKruskalBll(object): def demo(self): :return: # 1. 构建珠宝供应链网点实体 node_list [ LogisticsNode(0, 缅甸翡翠矿区A, 原料矿区), LogisticsNode(1, 云南分拣加工厂, 加工中心), LogisticsNode(2, 深圳总仓储中心, 仓储中心), LogisticsNode(3, 广州旗舰门店, 线下门店), LogisticsNode(4, 上海门店, 线下门店), LogisticsNode(5, 北京门店, 线下门店), ] # 2. Prim使用邻接矩阵单位千元0代表无直达线路 adj_matrix [ [0, 12, 28, 0, 0, 0], [12, 0, 8, 15, 0, 0], [28, 8, 0, 6, 18, 22], [0, 15, 6, 0, 25, 0], [0, 0, 18, 25, 0, 14], [0, 0, 22, 0, 14, 0] ] # 3. Kruskal使用原始边列表 raw_edges [ LogisticsEdge(0, 1, 12), LogisticsEdge(0, 2, 28), LogisticsEdge(1, 2, 8), LogisticsEdge(1, 3, 15), LogisticsEdge(2, 3, 6), LogisticsEdge(2, 4, 18), LogisticsEdge(2, 5, 22), LogisticsEdge(3, 4, 25), LogisticsEdge(4, 5, 14), ] # 4. 应用服务调用 print( Prim算法-稠密网点物流规划 ) prim_mst LogisticsRouteApplicationService.build_mst_by_prim(adj_matrix, node_list) prim_detail prim_mst.get_edge_detail() for start, end, cost in prim_detail: print(f{start} -- {end} 运输成本{cost}千元) print(f全网最低总成本{prim_mst.total_cost} 千元\n) print( Kruskal算法-稀疏跨城网点规划 ) krus_mst LogisticsRouteApplicationService.build_mst_by_kruskal(raw_edges, node_list) krus_detail krus_mst.get_edge_detail() for start, end, cost in krus_detail: print(f{start} -- {end} 运输成本{cost}千元) print(f全网最低总成本{krus_mst.total_cost} 千元)输出

Python: Prim Algorithms and Kruskal Algorithms

相关推荐

Linphone Android如何用异步架构重构通信体验：从卡顿瓶颈到毫秒级响应

替代料如何实现Pin-to-Pin上板即用

08-目标检测学习路线与模型选型指南（工控/嵌入式/机械臂场景）

更多资讯

Ekko Studio 安装与 Runtime 生命周期管理实战：Hermes Runtime、编码 Agent CLI 与桌面端升级迁移完全指南

同济计算机复试实战：流程拆解、面试博弈与避坑策略

RK3588 HDMI-IN方案怎么选？LT6911UXE、IT6616、RK628D对比

基于RTL8153的USB千兆网卡硬件设计与量产实战经验

PaddleHub 图像分类模型 resnet_v2_101_imagenet：安装、命令行预测与 Python API 实战指南

AI辅助简历制作全攻略：从ATS匹配到面试追问

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？