最小生成树算法详解课件.pptVIP

最小生成树算法------primKruskal1

生成树的概念生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。生成树不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成树2

最小代价生成树生成树的代价等于其边上的权值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V5125343

最小代价生成树两种常用的构造最小生成树的方法：普里姆算法（prim）克鲁斯卡尔算法（Kruskal）4

普里姆(Prim)算法假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v)中找一条代价最小的边(u0,v0),将其并入集合TE，同时将v0并入U集合。当U=V则结束，此时TE中必有n-1条边，则T=(V，{TE})为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止。5

V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-U｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)｛V1,V3,V6｝｛V2,V4,V5｝(2)｛V1,V3,V6,V4｝｛V2,V5｝(3)｛V1,V3,V6,V4,V2｝｛V5｝(4)｛V1,V3,V6,V4,V2,V5｝｛｝(5)最小代价生成树普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止6

V4V1V3V2V6V5165V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树7

V4V1V3V2V6V565V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V6｛V1,V3,V6｝｛V2,V4,V5｝(2)46554UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树8

V4V1V3V2V6V565V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V6｛V1,V3,V6｝｛V2,V4,V5｝(2)4655｛V1,V3,V6,V4｝｛V2,V5｝(3)262UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树9

V4V1V3V2V6V56V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6｛V1,V3,V6｝｛V2,V4,V5｝(2)465｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树10

V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)46｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5｛V1,V3,V6,V4,V2,V5｝｛｝(5)33UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树11

普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)4｛V1,V3,V6