最小生成ツリー(Primアルゴリズム)

            ，               。                   ，              ，
                  。

                ，     O( n^2 )，      。

    1.  ：       ，       V，    E；
    2.   ：Vnew = {x}，  x   V      （   ），Enew = {}  ；
    3.      ，  Vnew = V：
        (1).   E         ，  u   Vnew    ， v  Vnew    ，  v∈V（           ；
                       ，          ）；
        (2). v    Vnew ，      Enew ；
    4.  ：    Vnew Enew            。

    6           //    
    10          //   
    ABCDEF      //  
    A B 6 
    A C 1 
    A D 5 
    B C 5 
    C D 5 
    B E 3 
    E C 6 
    C F 4 
    F D 2 
    E F 6

    (A,C)(C,F)(F,D)(C,B)(B,E)

#include 
#include 
#include 
using namespace std;
#define VRType int
#define VertexType char
#define MAX_VERTEX_NUM 100

typedef struct ArcNode{
    int adjvex;
    VRType info;
    struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
}AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices[MAX_VERTEX_NUM];
    int vexnum, arcnum;
}ALGraph;

void CreatALGraph(ALGraph *&G)
{
    int i, t;
    char a, b;
    ArcNode *arc;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    cin>>G->vexnum>>G->arcnum;
    for(i=0; ivexnum; i++){
        cin>>G->vertices[i]->data;
        G->vertices[i]->firstarc = NULL;
    }
    for(i=0; iarcnum; i++){
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        cin>>a;
        cin>>b;
        cin>>arc->info;
        arc->adjvex = b-'A';
        t = a-'A';
        arc->nextarc = G->vertices[t]->firstarc;
        G->vertices[t]->firstarc = arc;
    }
}

struct{
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

void Prim(ALGraph *G)
{

    int i, j, k=0, min;
    for(i=0; ivexnum; i++){
        closedge[i].adjvex = G->vertices[i]->data;
        closedge[i].lowcost = INT_MAX;
    }
    closedge[0].lowcost = 0;
    ArcNode *arc;
    for(i=1; ivexnum; i++){
        min = INT_MAX;
        arc = G->vertices[k]->firstarc;
        while(arc){
            if((closedge[arc->adjvex].lowcost) && (arc->info < closedge[arc->adjvex].lowcost)){
                closedge[arc->adjvex].adjvex = G->vertices[k]->data;
                closedge[arc->adjvex].lowcost = arc->info;
            }
            arc = arc->nextarc;
        }
        for(j=0; jvexnum; j++)
            if((closedge[j].lowcost) && (closedge[j].lowcostcout<<'('<','<vertices[k]->data<<')';
        closedge[k].lowcost = 0;
    }
    cout<int main()
{
    ALGraph *g;
    CreatALGraph(g);
    Prim(g);
    return 0;
}