图最小生成树prim算法.ppt

基本图算法 陈嘉庆 最小生成树问题 最小生成树 1回便的 无向图 生成树1 生成树2 一个有n个结点的连通图的生成树是原图的 极小连通子图,且包含原图中的所有n个结 点,并且有保持图连通的最少的边 最小生成树可以用 kruskal(克鲁斯卡尔) 算法或prim普里姆)算法求出 最小生成树算法的目标:一个n个点的图, 选若干条边(一定是n-1条)使得图连在 起,并且所有选中的边的长度和最小 最小生