贪心算法(图算法).ppt

Algorithms
贪心算法之图算法
刘伟(Sunny)
weiliu_china@
内容
最小生成树
单源最短路径
思考
若要将n个城市之间原有的公路改造为高速公路,这些城市之间原有公路网如右图所示。如何以最低的成本来构建高速公路网,使得任意两个城市之间都有高速公路相连?
最小生成树
最小生成树
最小生成树
Minimal Spanning Trees (MST)
任何只由G的边构成,并包含G的所有顶点的树称为G的生成树(G连通)。加权无向图G的生成树的代价是该生成树的所有边的代价(权)的和,最小代价生成树是其所有生成树中代价最小的生成树。
最小生成树
Prim算法:时间复杂度O(|V|2+|E|),O(|E|log|V|)
Kruskal算法:时间复杂度O(|E|log|E|)
算法的选择:
从图的稀疏程度考虑(稠密图Prim,稀疏图Kruskal或Prim + Heap)
最小生成树
Prim算法
(1) 任意选定一点s,设集合S={s}
(2) 从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短,则(i,j)就是生成树上的一条边,同时将j点加入S
(3) 转到(2)继续进行,直至所有点都己加入S集合
最小生成树
Prim算法
5
0
4
6
1
3
2
10
25
14
24
22
16
18
5
0
4
6
1
2
10
25
14
22
16
12
3
12
28
最小生成树
Prim算法
练****公路造价
现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。在分析了这张图后发现,任一对城市都是连通的。现在要求用公路把所有城市联系起来,如何设计可使得工程的总造价最少?
最小生成树
Prim算法
练****公路造价
【输入格式】
第一行两个数v(v<=200)和e分别代表城市数和边数,以下e行,每行为两个顶点和它们之间的边权w(w<1000)。
【输出格式】
v-1行,每行为两个城市的序号,表明这两个城市间建一条公路,再加该公路的造价。