实验报告Prim与Kruskal算法.doc
    1.问题
    [描述算法问题，首选形式化方式（数学语言），其次才是非形式化方式（日常语言）]
    带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。综合以上两个概念，我们可以得出：构造连通网的最小代价生成树，即最小生成树。
    解析
    [问题的理解和推导，可用电子版直接在此编写，也可用纸笔推导，拍照嵌入本文档]
    对于Prim算法：
    假设G=(V,E)为一网图，其中V为顶点的集合，E为边的集合。从某一顶点u1出发选择与它关联的具有最小权值的边(u1, v)，将其顶点v加入到生成树顶点，集合U中。U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。
    令集合U的初值为U={u1} (假设构造最小生成树时，从顶点u1出发)，集合T的初值为T={ }。
    以后每一步从U中选择一个顶点u（u属于U），而另一个顶点v属于V-U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u,v）加入集合T中，如此不断重复，直到U=V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。
    对于Kruskal算法：
    （1）建图，构造Kruskal边集，边集元素应该包括该边的起始顶点、终止顶点、权值；
    （2）将边集按权值从小到大的顺序进行排序；
    （3）从小到大依次从Kruskal边集中取边加入最小生成树集合，判断条件：将该边加入最小生成树集合，与生成树集合中原有的边不构成环；
    （4）最小生成树集合中元素（构成生成树的边）的个数为原图顶点数-1时，代表最小生成树构造完毕。

    2.设计
    [核心伪代码]
    Prim(G)
    //构造最小生成树的Prim算法
    Vr <— {V。}
    Er<— 空集
    for i <— 1 to |V| —1 do
    在所有的边(v,u)中，求权重最小的边e=(v,u)
    使得v在Vr中，而u在V—Vr中，
    Vr <—Vr U {u    }
    Er <—Er U {e*}
    return Er

    Kruskal(G)
    按照边的权重w(ei1)≤…..≤w(wi|E|)的非递减顺序对集合E排序
    Er <—空集：ecounter<— 0 //初始化树中边的顶点集合以及集合的规模
    k <— 0 //初始化已处理的边的数量
    while ecounter < |V|—1 do
    k <— k+1
    if Er U {eik}无回路
    Er <— Er U {er}: ecounter <— ecounter + 1
    return Er
    3.分析
    [算法复杂度推导]
    Prim: (|V| - 1+|E|)O(log|V|) = O(|E|log|V|)
    Kruskal: O(|E|log|E|)
    4.源码
    https://github.com/joserfdave/arithmetic/tree/main