最小生成树与最短路径问题-课件（PPT·精·选）.ppt

Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 图——最小生成树与最短路径问题 2009/05/14 2 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 基于邻接表的图操作运算 3 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 基于邻接表的图操作运算 4 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 5 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 主要内容?生成树的概念( spanning tree ) ? Prim 算法? Kruskal 算法?最短路径问题? Dijkstra 算法? Floyd 算法 6 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 生成树(支撑树)的概念 GraphMatrix graph = { 6, { {0, 10, M, M, 19,21}, {10, 0, 5, M, M, 11}, {M, 5, 0, M, M, M}, {M, M, M, 0, 18, 14}, {19, M, M, 18, 0, 33}, {21, 11, M, 14, 33, 0} } }; 012345 子图+ 连通+ 无环 7 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 无向图中无环的充要条件?检查每一个连通分枝?对于所有连通分枝: 顶点数–边的数目= 1 可以采用周游算法。算法复杂度: n 0123458 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng 最小生成树 Minimum-cost Spanning Tree ?连通无向带权图——网络。?网络(带权图)的生成树中生成树各边的权值加起来称为生成树的权,把权值最小的生成树称为最小生成树。 ( 简称为 MST) 。9 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng ?G=(V ,E)是一个网络, U是顶点集合 V的一个真子集。?如果 u∈U,v∈V-U ,且边(u,v) 是图 G中所有一个端点在U里,另一端点在 V-U 里的边中权值最小的边, 则一定存在 G的一棵最小生成树包括此边(u,v) 。 MST 必包含连通图中任意两个顶点划分之间的最小权的边。(任意割集中的最小边) MST 性质 10 Hu Junfeng Hu Junfeng Hu Junfeng Hu Junfeng MST 性质证明(反证法) uu ′ vv ′U V-U v? v ?边(u,v )是图 G中所有一个端点在 U里,另一端点在 V-U 里的边中权值最小的边。?假设:存在 G的一棵最小生成树不包括此边。