生成树与最小生成树

生成树,对图遍历访问的一条无回路的遍历路径称为图的生成树,生成树不是唯一的,深度优先和广度优先的访问路径就是一棵生成树.深度优先搜索与广度优先搜索的生成树分别称为***,

最小生成树:对带有权值的图,生成树路径中权值总和最小的路径,称为最小生成树.求最小生成树的算法有 prim算法 和 ***:

 prim算法:
假设图G=(V,E)是有n个顶点的连通图. T=(U,TE)是G的最小生成树,初值为空.首先从V中任选一个顶点放入U.(标记1:)然后从E中取一条边放入TE,这条边要满足:其中一个顶点在U中,一个再U之外(没在U中)的集合(这样的边不止一条)中权值最小的那条.然后把不在U的顶点放入U.jump 标记1. 直到V中所有点都在U中, 这时TE中有n-1条边.最小生成树算法结束.算法时间复杂度是O(n2)