一，大致的遍历过程图解及过程讲解

先从某一点开始寻找与其他边连接最小的边

1，如下图（b）中，A与其它五点中C的距离最短，所以连接AC；

2，图（c）将AC相比较，看谁与剩下点相连距离较短则替代，

      如AB=6，CB=5，所以取CB； AE,AF都不相连，而CE,CF都相连所以取AE,AF;

     此时比较AC与其它四点连接中距离最短的，所以连接CF；

3，图（d）将ACF相比较，看谁与剩下点相连距离较短则其替代，

     如AD=5，FD=2，所以取FD；CE=6，FE=6，所以不管还用CE，F点B点无连接

     此时比较ACF与其它三点连接中距离最短的，所以连接FD；

4，。。。。。。（按照上面方法进行寻找最小）。

二，实现方法

这种方法除了构造邻接矩阵所需的结构体和函数之外，新加入一个closedge结构体，数组中每一个顶点代表一个点到A的距离。

包含了对应顶点adjvex和权值lowcost。

        3代表顶点D

        eg:closedge[3]={A,5} 即代表3位置的顶点到A的距离为5，即DA=5。

              此时若DC=3，则替换原来的A，变成closedge[3]={C,3};

 

第一步：先构造邻接矩阵，并赋值，该过程类似于图的邻接矩阵储存法类似。

第二步，先将遍历开始顶点与其余所有顶点的权赋值到closedge中，然后进行下面循环。

第三步：找到closedge数组中closedge[I].lowcost中最小的值所对应的位置n（即为closedge[I].adjvex），然后将的权值lowcost变成0，即代表两点连接。

第四步：将n与所有点连接的距离与closedge进行对比，如果比closedge小则对应替换。

然后再跳到第二步，进行下次循环，总共循环（顶点数-1）次。

此部分可能写的不是特别好，但是需要讲的都在最上面的图解里或者可以看下面运行截图。

三，实现截图

如下图所示：每次遍历出的closedge即为每次替换后将要比较并取出最小值的。

四，代码

#include<iostream>
using namespace std;

#define pointMax 100
#define cloEdge 100

typedef struct Node
{
    char adjvex;                       //在图中的哪个顶点
    int lowcost;                       //权值
}closeedge[cloEdge];

struct AMgroup
{
    char VTchart[pointMax];                  //顶点表
    int AMchart[pointMax][pointMax];         //邻接矩阵
    int point, vert;                         //点，边
}; 

int AMlocate(AMgroup &A, char x)                        //找到某一顶点的位置
{
    for (int i = 0; i < A.point; i++)
    {
        if (A.VTchart[i] == x)
        {
            return i;
            break;
        }
    }
    cout << "error；";
    return -1;
}

void CreatAM(AMgroup &A)                      //构造邻接矩阵
{
    cout << "输入邻接矩阵顶点数：";
    cin >> A.point;
    cout << "输入邻接矩阵边数：";
    cin >> A.vert;
    getchar();

    char a[100];
    cout << "输入点的信息：";
    gets_s(a);
    for (int i = 0; i < A.point; i++)             //依次输入点的信息
    {
        A.VTchart[i] = a[i];
    }
    for (int i = 0; i < A.point; i++)              //初始换邻接矩阵，边的权值均设为最大
    {
        for (int j = 0; j < A.point; j++)
        {
            A.AMchart[i][j] = -1;
        }
    }

    char v1, v2; int len;
    for (int i = 1; i <= A.vert; i++)               //构造邻接矩阵
    {
        cout << "输入第" << i << "条边的两个顶点以及权值：";
        cin >> v1 >> v2 >> len;
        int m, n;
        m = AMlocate(A, v1);
        n = AMlocate(A, v2);
        A.AMchart[m][n] = A.AMchart[n][m] = len;
    }
}

int k, j;

int Min(AMgroup &A,Node *closeedge)
{
    int a = 32767;
    int c;
    cout << endl;
    cout << "closeedge结构体数组遍历：" << endl;
    for (int i = 0; i < j; i++)
    {
        cout<<A.VTchart[i]<<"      "<<closeedge[i].adjvex <<"    "<<closeedge[i].lowcost << endl;
        if (closeedge[i].lowcost < a  && closeedge[i].lowcost>0)           //如果closeedge[i].lowcost小于之前遍历的最小值且未被遍历
        {
            a = closeedge[i].lowcost;
            c = i;
        }
    }
    return c;
}

void MSTPrim(AMgroup &A, char m)                   //普利姆算法
{
    Node *closeedge = new Node;
    k = AMlocate(A, m);
    for (j = 0; j < A.point; j++)                   //赋值
    {
        closeedge[j] = { m, A.AMchart[k][j] };           //每个点到所求点的距离
    }
    closeedge[k].lowcost = 0;                          //自己到自己初始化为0

    char u0, v0;
    for (int i = 1; i < A.point; i++)
    {
        k = Min(A,closeedge);                          //找到距离该点距离最短的位置
        u0 = closeedge[k].adjvex;                      //最小边的一个顶点
        v0 = A.VTchart[k];                             //最小边的另一个顶点
        cout <<k-1<<"点最小。"<<"本次遍历边："<< u0 << "---" << v0 << endl;

        closeedge[k].lowcost = 0;                      //第K个顶点并入
        for (j = 0; j < A.point; j++)
        {
            if ((A.AMchart[k][j] < closeedge[j].lowcost && A.AMchart[k][j]>0)
                || (A.AMchart[k][j]>0 && closeedge[j].lowcost<0))             //新点周围与远点周围进行判断
            {
                closeedge[j] = { A.VTchart[k], A.AMchart[k][j] };
            }
        }
    }
}

int main()
{
    AMgroup *A = new AMgroup;
    CreatAM(*A);
    char m;
    cout << "输入开始遍历的值：";
    cin >> m;
    MSTPrim(*A, m);
    getchar();
    return 0;
}