、典型用途: 欲在n个城市间建立通信网,则n个城市应铺n-1条线路;但因 为每条线路都会有对应的经济成本,而n个城市可能有 n(n-1)/2条线路,那么,如何选择条线路使总费用最少? 先建立数学模型: 顶点 表示城市,有n个; 边—表示线路,有n-1条; 显然此连通网是 边的权值一表示线路的经济代价 生成 连通网表n个规市间的通信网 问题抽象:n个顶点的生成树很多,需要从中选一棵代价最 小的生成树,即该树各边的代价之和最小。此树便称为最小 生成树MST。8 欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因 为每条线路都会有对应的经济成本，而n个城市可能有 n(n-1)/2 条线路，那么，如何选择n–1条线路使总费用最少？ 4、典型用途： 先建立数学模型： 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间的通信网。 显然此连通网是 一棵生成树！ 问题抽象：n个顶点的生成树很多，需要从中选一棵代价最 小的生成树，即该树各边的代价之和最小。此树便称为最小 生成树MST