图的应用：最小生成树
最小生成树的定义：最小生成树的性质：Prime算法：（贪心算法思想）Prime算法的代码实现原理：Prime算法的实现代码：Prime算法的性能：Kruskal算法：（贪心算法思想）Kruskal算法的实现原理：Kruskal算法的代码实现：Kruskal算法的性能：算法性能对比：最小生成树的定义：
最小生成树的性质：
1、不唯一性：
Prime算法：（贪心算法思想）
要点:
1、具有最小权值2、无回路3、初始结果集为空
Prime算法的代码实现原理：
min_weight[n]:表示定点数量的大小，已挑选顶点到未挑选顶点权值最小的边
adjvex[n]:表示是哪个顶点将这条边引入的
Prime算法的实现代码：
void MST_Prime(Graph G){//俩个辅助数组int min_weight[G.vexnum];int adjvex[G.vexnum];//初始化俩个辅助数组for(int i=0;i<G.vexnum;i++){min_weight[i] = G.Edge[0][i];adjvex[i] = 0;}int min_arc;//表示挑选的最小边int min_vex;//表示挑选边的另一个顶点(数组下标)for(int i=1;i<G.vexnum;i++){//循环n-1次，将剩下的n-1个顶点加入结果树min_arc = MAX;//将最小边的长度置为无穷大，用于比较for(int j=1;j<G.vexnum;j++)//挑选满足条件的边，以及此边的顶点if(min_weight[j] != 0 && min_weight[j] < min_arc){min_arc = min_weight[j];min_vex = j;}min_weight[min_vex] = 0;//加入后给此边长度置0for(int j=0;j<G.vexnum;j++){//加入新节点后修改其他数组的值if(min_weight[j] != 0 && G.Edge[min_arc][j] < min_weight[j]){min_weight[j] = G.Edge[min_arc][j];adjvex[j] = min_arc;}}}}
Prime算法的性能：
时间复杂度：O(|V|2)
适用于稠密图，因为时间复杂度与边无关
Kruskal算法：（贪心算法思想）
ps：numS表示连通分量，当其大于1不是一颗最小生成树
要点：
1、具有最小权值2、无回路3、初始结果集为所有节点
Kruskal算法的实现原理：
堆排序sort() + 并查集
Kruskal算法的代码实现：
typedef struct Edge{int a,b;//边的俩个顶点下标 int weight;//权重 };void MST_Kruskal(Graph G,Edge* edges,int* parent){//图，边的集合，辅助变量 heap_sort(edges);//堆排序Initial(parent);//初始化parent=-1for(int i=0;i<G.arcnum;i++){//边的数量 int a_root = Find(parent,edges[i].a);//求第一个端点的根节点 int b_root = Find(parent,edges[i].b);//求第二个端点的根节点 if(a_root != b_root)Union(parent,a_root,b_root);//不相等加入结果集 }}
ps：这里未实现的函数在前几期博客中存在
Kruskal算法的性能：
时间复杂度：O(|E|log|E|)
更适用于稀疏图，因为时间复杂度只与边有关
