go:Prim Algorithms and Kruskal Algorithms

项目结构/* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:04 # User : geovindu # Product : GoLand # Project : goalgorithms # File : aggregate_root.go */ package common // AggregateRoot 聚合根顶层抽象 type AggregateRoot struct { domainEvents []interface{} } // GetDomainEvents 获取领域事件 func (ar *AggregateRoot) GetDomainEvents() []interface{} { copyEvents : make([]interface{}, len(ar.domainEvents)) copy(copyEvents, ar.domainEvents) return copyEvents } // ClearDomainEvents 清空领域事件 func (ar *AggregateRoot) ClearDomainEvents() { ar.domainEvents ar.domainEvents[:0] } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:05 # User : geovindu # Product : GoLand # Project : goalgorithms # File : entity.go */ package common // Entity 实体顶层抽象拥有唯一ID type Entity struct { id int } // NewEntity 创建实体 func NewEntity(id int) Entity { return Entity{id: id} } // ID 获取实体唯一标识 func (e Entity) ID() int { return e.id } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:05 # User : geovindu # Product : GoLand # Project : goalgorithms # File : value_object.go */ package common // ValueObject 值对象顶层抽象不可变基于属性相等判断 type ValueObject interface { Equal(other ValueObject) bool } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:06 # User : geovindu # Product : GoLand # Project : goalgorithms # File : domain_err.go */ package common import fmt // DomainErr 统一领域业务异常 type DomainErr struct { Msg string } func (e *DomainErr) Error() string { return fmt.Sprintf([领域异常] %s, e.Msg) } // NewDomainErr 构造领域异常 func NewDomainErr(msg string) error { return DomainErr{Msg: msg} } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:06 # User : geovindu # Product : GoLand # Project : goalgorithms # File : union_find.go */ package common // UnionFind 并查集路径压缩Kruskal算法依赖 type UnionFind struct { parent []int } // NewUnionFind 初始化并查集 func NewUnionFind(size int) *UnionFind { parent : make([]int, size) for i : 0; i size; i { parent[i] i } return UnionFind{parent: parent} } // Find 查找根节点路径压缩 func (uf *UnionFind) Find(x int) int { if uf.parent[x] ! x { uf.parent[x] uf.Find(uf.parent[x]) } return uf.parent[x] } // Union 合并两个集合true合并成功无环false成环 func (uf *UnionFind) Union(x, y int) bool { rootX : uf.Find(x) rootY : uf.Find(y) if rootX rootY { return false } uf.parent[rootY] rootX return true } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:07 # User : geovindu # Product : GoLand # Project : goalgorithms # File : logistics_node.go */ package model import goalgorithms/primkruskal/common // LogisticsNode 物流网点【实体】 // 代表珠宝供应链节点矿区、加工厂、仓储、线下门店 type LogisticsNode struct { common.Entity nodeName string // 网点名称 nodeCategory string // 网点类型原料矿区/加工中心/仓储中心/线下门店 } // NewLogisticsNode 构造网点实体 func NewLogisticsNode(id int, name, category string) LogisticsNode { return LogisticsNode{ Entity: common.NewEntity(id), nodeName: name, nodeCategory: category, } } // NodeName 获取网点名称 func (n LogisticsNode) NodeName() string { return n.nodeName } // NodeCategory 获取网点类型 func (n LogisticsNode) NodeCategory() string { return n.nodeCategory } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:07 # User : geovindu # Product : GoLand # Project : goalgorithms # File : logistics_edge.go */ package model import goalgorithms/primkruskal/common // LogisticsEdge 物流线路【值对象】 // 两点间运输链路cost为综合成本路费押运保险货品损耗单位千元 type LogisticsEdge struct { startID int endID int cost float64 } // NewLogisticsEdge 构造线路值对象 func NewLogisticsEdge(start, end int, cost float64) LogisticsEdge { return LogisticsEdge{ startID: start, endID: end, cost: cost, } } func (e LogisticsEdge) Equal(other common.ValueObject) bool { oe, ok : other.(LogisticsEdge) if !ok { return false } return e.startID oe.startID e.endID oe.endID e.cost oe.cost } func (e LogisticsEdge) StartID() int { return e.startID } func (e LogisticsEdge) EndID() int { return e.endID } func (e LogisticsEdge) Cost() float64 { return e.cost } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:08 # User : geovindu # Product : GoLand # Project : goalgorithms # File : logistics_mst.go */ package model import goalgorithms/primkruskal/common // LogisticsMST 最小生成树【聚合根】 // 聚合全部网点、MST选中线路、总运输成本 type LogisticsMST struct { common.AggregateRoot AllNodes []LogisticsNode MstEdges []LogisticsEdge TotalCost float64 } // SetNodes 绑定全部网点 func (m *LogisticsMST) SetNodes(nodes []LogisticsNode) { m.AllNodes nodes } // SetMstResult 写入MST计算结果 func (m *LogisticsMST) SetMstResult(edges []LogisticsEdge, totalCost float64) { m.MstEdges edges m.TotalCost totalCost } // GetEdgeDetail 格式化线路详情[(起点名,终点名,成本)] func (m *LogisticsMST) GetEdgeDetail() [][3]interface{} { nodeMap : make(map[int]string, len(m.AllNodes)) for _, node : range m.AllNodes { nodeMap[node.ID()] node.NodeName() } var res [][3]interface{} for _, edge : range m.MstEdges { sName : nodeMap[edge.StartID()] eName : nodeMap[edge.EndID()] res append(res, [3]interface{}{sName, eName, edge.Cost()}) } return res } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:08 # User : geovindu # Product : GoLand # Project : goalgorithms # File : prim.go */ package algorithm import ( goalgorithms/primkruskal/common goalgorithms/primkruskal/domain/model math ) // PrimAlgorithm Prim最小生成树【领域算法服务】 // 适用稠密图、门店/加工厂密集场景 type PrimAlgorithm struct{} // Calculate 执行Prim计算返回MST线路、总成本、领域异常 func (p PrimAlgorithm) Calculate(adjMatrix [][]float64, nodes []model.LogisticsNode) ([]model.LogisticsEdge, float64, error) { nodeCnt : len(nodes) if nodeCnt 0 { return nil, 0, common.NewDomainErr(网点集合不能为空无法生成物流路网) } const INF math.MaxFloat64 inMST : make([]bool, nodeCnt) minDist : make([]float64, nodeCnt) preNode : make([]int, nodeCnt) for i : range minDist { minDist[i] INF preNode[i] -1 } minDist[0] 0 totalCost : 0.0 var mstEdges []model.LogisticsEdge for round : 0; round nodeCnt; round { // 选取距离MST最近未加入节点 selectIdx : -1 minVal : INF for i : 0; i nodeCnt; i { if !inMST[i] minDist[i] minVal { minVal minDist[i] minVal minDist[i] selectIdx i } } if selectIdx -1 { return nil, 0, common.NewDomainErr(网点图不连通无法构建完整物流最小生成树) } inMST[selectIdx] true totalCost minVal // 记录边 preIdx : preNode[selectIdx] if preIdx ! -1 { edge : model.NewLogisticsEdge(preIdx, selectIdx, adjMatrix[preIdx][selectIdx]) mstEdges append(mstEdges, edge) } // 松弛更新邻接点距离 for j : 0; j nodeCnt; j { w : adjMatrix[selectIdx][j] if !inMST[j] w 0 w minDist[j] { minDist[j] w preNode[j] selectIdx } } } return mstEdges, totalCost, nil } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:09 # User : geovindu # Product : GoLand # Project : goalgorithms # File : kruskal.go */ package algorithm import ( goalgorithms/primkruskal/common goalgorithms/primkruskal/domain/model sort ) // KruskalAlgorithm Kruskal最小生成树【领域算法服务】 // 适用稀疏图、跨城分散门店、矿区组网 type KruskalAlgorithm struct{} // Calculate 执行Kruskal计算 func (k KruskalAlgorithm) Calculate(edges []model.LogisticsEdge, nodes []model.LogisticsNode) ([]model.LogisticsEdge, float64, error) { nodeCnt : len(nodes) if nodeCnt 0 { return nil, 0, common.NewDomainErr(网点集合不能为空无法生成物流路网) } // 边升序排序 sort.Slice(edges, func(i, j int) bool { return edges[i].Cost() edges[j].Cost() }) uf : common.NewUnionFind(nodeCnt) var mstEdges []model.LogisticsEdge totalCost : 0.0 for _, e : range edges { if uf.Union(e.StartID(), e.EndID()) { mstEdges append(mstEdges, e) totalCost e.Cost() if len(mstEdges) nodeCnt-1 { break } } } if len(mstEdges) ! nodeCnt-1 { return nil, 0, common.NewDomainErr(网点图不连通无法构建完整物流最小生成树) } return mstEdges, totalCost, nil } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:09 # User : geovindu # Product : GoLand # Project : goalgorithms # File : logistics_route_service.go */ package application import ( goalgorithms/primkruskal/domain/algorithm goalgorithms/primkruskal/domain/model ) // LogisticsRouteApplicationService 物流路线应用服务 // 职责编排调用领域算法、组装聚合根对外提供统一业务接口 type LogisticsRouteApplicationService struct{} // BuildMSTByPrim Prim生成最小生成树 func (l LogisticsRouteApplicationService) BuildMSTByPrim(matrix [][]float64, nodes []model.LogisticsNode) (*model.LogisticsMST, error) { prim : algorithm.PrimAlgorithm{} edges, cost, err : prim.Calculate(matrix, nodes) if err ! nil { return nil, err } mst : model.LogisticsMST{} mst.SetNodes(nodes) mst.SetMstResult(edges, cost) return mst, nil } // BuildMSTByKruskal Kruskal生成最小生成树 func (l LogisticsRouteApplicationService) BuildMSTByKruskal(edges []model.LogisticsEdge, nodes []model.LogisticsNode) (*model.LogisticsMST, error) { krus : algorithm.KruskalAlgorithm{} edges, cost, err : krus.Calculate(edges, nodes) if err ! nil { return nil, err } mst : model.LogisticsMST{} mst.SetNodes(nodes) mst.SetMstResult(edges, cost) return mst, nil }调用/* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述 Prim Algorithms and Kruskal Algorithms 普里姆算法和克鲁斯卡尔算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/8/7 23:10 # User : geovindu # Product : GoLand # Project : goalgorithms # File : primkruskalbll.go */ package bll import ( fmt goalgorithms/primkruskal/application goalgorithms/primkruskal/domain/model log ) func PrimkruskalMain() { // 1. 初始化珠宝供应链网点实体 nodeList : []model.LogisticsNode{ model.NewLogisticsNode(0, 缅甸翡翠矿区A, 原料矿区), model.NewLogisticsNode(1, 云南分拣加工厂, 加工中心), model.NewLogisticsNode(2, 深圳总仓储中心, 仓储中心), model.NewLogisticsNode(3, 广州旗舰门店, 线下门店), model.NewLogisticsNode(4, 上海门店, 线下门店), model.NewLogisticsNode(5, 北京门店, 线下门店), } // 2. Prim 邻接矩阵 单位千元0无直达线路 adjMatrix : [][]float64{ {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 原始边列表 rawEdges : []model.LogisticsEdge{ model.NewLogisticsEdge(0, 1, 12), model.NewLogisticsEdge(0, 2, 28), model.NewLogisticsEdge(1, 2, 8), model.NewLogisticsEdge(1, 3, 15), model.NewLogisticsEdge(2, 3, 6), model.NewLogisticsEdge(2, 4, 18), model.NewLogisticsEdge(2, 5, 22), model.NewLogisticsEdge(3, 4, 25), model.NewLogisticsEdge(4, 5, 14), } appService : application.LogisticsRouteApplicationService{} // Prim算法执行 fmt.Println( Prim算法-稠密网点物流规划 ) primMST, err : appService.BuildMSTByPrim(adjMatrix, nodeList) if err ! nil { log.Fatal(err) } primDetail : primMST.GetEdgeDetail() for _, item : range primDetail { fmt.Printf(%s -- %s 运输成本%.0f千元\n, item[0], item[1], item[2]) } fmt.Printf(全网最低总成本%.0f 千元\n\n, primMST.TotalCost) // Kruskal算法执行 fmt.Println( Kruskal算法-稀疏跨城网点规划 ) krusMST, err : appService.BuildMSTByKruskal(rawEdges, nodeList) if err ! nil { log.Fatal(err) } krusDetail : krusMST.GetEdgeDetail() for _, item : range krusDetail { fmt.Printf(%s -- %s 运输成本%.0f千元\n, item[0], item[1], item[2]) } fmt.Printf(全网最低总成本%.0f 千元\n, krusMST.TotalCost) }代码实现了珠宝供应链物流网络的最小生成树(MST)优化方案包含Prim和Kruskal两种算法。代码采用领域驱动设计(DDD)架构包含实体、值对象、聚合根等核心概念。主要功能定义物流节点实体(LogisticsNode)和边值对象(LogisticsEdge)实现Prim算法(稠密图优化)和Kruskal算法(稀疏图优化)提供应用服务层统一接口计算并输出MST路径和最低总成本示例演示了6个节点(矿区、加工厂、仓储、门店)的物流网络优化分别用两种算法计算最优运输路线和成本。输出显示各节点间最优连接方式及全网最低运输总成本。输出