Prim算法
keyword：从一个顶点起，顺顶点寻找，完成最小生成树的构建
算法描述：从一个顶点开始，寻找与该结点连接的且不是弦且未被选中过的最短路，然后进入下一个结点，直到所有结点都被加入到生成树中。
顶点的随机可以随机，prim算法保证任意选择都会得到正确的最小生成树。
在教材中，使用到了辅助数组，释义
其实使用的是一个结构体一维数组，array记录了i结点目前距离树最近距离及结点，后面需要回溯时使用表格为依据，可完成快速跳转，每一次选择lowcost最小的结点i放入U中。
struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];
使用不断更新这个表格，按照prim算法就可以得到最小生成树。
代码部分就是更新k，选择结点，应该根据具体问题书写。
Kruskal算法
算法描述：最小生成树中，长度较小的边一定存在，将所有边按照长度顺序排列，将满足条件的边及结点分别加入到树中，直到所有结点都被加入到树种，这样也能得到唯一正确的最小生成树。
keyword：边优先的最小生成树算法
满足条件：是至少存在一个不在树中结点的最短弦
将边按长度进行排序(根据这一题的性质，可以选择堆排序)，取出，检查合法性，合法则加入到图中，不合法再次取出，直到堆空。
预览时标签不可点收录于话题#个上一篇下一篇