当前位置：首页
> 最小生成树
最小生成树—Prim（普里姆）算法
一、算法概述Prim 算法是一种用于求解加权无向连通图的最小生成树（MST） 的贪心算法。它从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集的最小权重边。二、算法思想初始化：从任意顶...
最小生成树—Kruskal（克鲁斯卡尔）算法
一、算法描述在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。二、核心思想贪心策略：每次从未选择的边中，选取一条权值最小的边。避免环路：如果加入...
最小生成树—基本概念
一、最小生成树核心概念1. 基本定义一个带权无向连通图的最小生成树，是指从该图中选择若干条边，构成一个包含图中所有顶点的树结构（无环、连通），且所有选中边的权值之和最小。2. 关键性质生成树的本质：包...