最小生成树 １．是一棵树 ２．无回路 ３．Ｎ个顶点一定有Ｎ－１条边 ４．包含全部顶点 ５．Ｎ－１条边都在图里 ６．边的权重和最小
生成约束： １．只能用图里有的边 ２．只能正好用掉Ｎ－１条边 ３．不能有回路
主要算法：
PRim算法 －－ 让树长大
int prim(int n) { memset(vis,false,sizeof(vis));//标记数组清零 for(int i=1; i<=n; i++) { dis[i] = arr[1][i];//从1号节点开始生成树 } int ans = 0;//距离权值总和 vis[1] = true;//生成树的根（起点）标记访问过 for(int i=2; i<=n; i++)//要生成n-1条边，所以循环n-1次 { int pos = i;//用来记录每一次循环找到的节点编号 int Min = INF;//无穷大 for(int j=1; j<=n; j++)//对dis数组进行遍历找到距离最小的 { if(vis[j]==false && dis[j] < Min)//如果该点未被访问过，并且距离更小 { Min = dis[j];//更新最小距离 pos = j;//记录节点编号 } } ans += Min;//加上找到的最小权值 vis[pos] = true;//标记找到的该点被访问 for(int j=1; j<=n; j++)//更新dis数组 { if(vis[j]==false && dis[j] > arr[pos][j])//如果该点未被访问过且距离更大 { dis[j] = arr[pos][j];//更新生成树到该点的距离 } } } return ans;//得出权值总和 }Kruskal算法 ——— 将森林变为树
新闻热点
疑难解答
