图论算法中的最小生成树问题

图论算法-最小生成树

在无向图中确定一个最小生成树（minimum spanning tree），这一问题对于有向图同样具有研究价值，但求解过程更为复杂。只有当图G具备连通性时，才能确保最小生成树的存在。此外，在构成最小生成树的结构中，所包含的边的数量恒等于顶点数\left | V \right |减一。

Prim算法

在每一个步骤中，都需要将一个节点视为根节点，并在其上方添加边。在算法运行的任意时刻，都可以观察到一组已经被加入到树结构中的顶点，而其他顶点则尚未被纳入该树。此时，算法在每个阶段均可通过选取边(u,v)，其中该边的权重是所有满足u属于树而v不属于树的边中最小的一个，从而找到一个新的顶点，并将其纳入到这棵树中。

代码

本部分所采用的数据结构为邻接矩阵。

    void Prim(Graph g)
    {
    VertexType adjver[VERNUM];
    WeightType lowcost[VERNUM];
    int i, j, k;
    WeightType min;
    
    // 初始化，一开始生产树中只有开始的顶点
    // 这里开始的顶点的编号为 0
    for (i = 0; i < g->vernum; i++)
    {