最小生成树 贪心法 对图G=v,E)的每一条 边e∈E赋以相应的实数 权o(e),得到一个网 最小生成树Prm算法 络,记为N=Vv,E,W 算法Prim(G,E 设T=(VE)是N的一个生 (215354成树包括原图所有顶点 l.S←{1 2. while js②do 的连通树),树T的权为 3.从S中选择j使得到S中顶点的边权最小 N中权最小的生成树称为 N的最小生成树。 贪心法 贪心法 最小生成树Prim算法 ●最小生成树 Krusca算法 算法 Kruskal(G,W) 1.按照权从小到大顺序排序G中的边 2.fori← 1 to m do 3.如果e的两个端点不在同一个连通分 则将e加到T中 贪心法 贪心法一般原则 最小生成树 Kruskal算法 贪心法得到的可能是最优解 ·最小生成树 部分背包问题 贪心法是否求得最优解需要数学证明 问题规模太大,最优解代价太高时,用贪 ·地图着色 ·巡回售货员问题9 最小生成树 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 对图G=(V, E) 的每一条 边 赋以相应的实数 权 ，得到一个网 络，记为N=(V, E, W) 设T=(V, E’)是N的一个生 成树(包括原图所有顶点 的连通树)，树T的权为 N中权最小的生成树称为 N的最小生成树。 e∈ E ω(e) ∑∈ = ' ( ) ( ) e E W T ω e 贪心法 z最小生成树Prim算法 贪心法 z最小生成树Prim算法 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 1 2 3 4 5 6 1 4 4 2 2 5 5 3 贪心法 z最小生成树Kruscal算法 贪心法 z最小生成树Kruskal算法 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 1 2 3 4 5 6 1 3 2 4 5 贪心法一般原则 z 贪心法得到的可能是最优解 z 最小生成树 z Huffman树 z 部分背包问题 z 贪心法是否求得最优解需要数学证明 z 问题规模太大，最优解代价太高时，用贪 心法求近似解 z 地图着色 z 巡回售货员问题