数据结构学习笔记（四） 图之邻接表实现最小生成树prim算法

以下是使用邻接表存储表示的，最小生成树prim算法的应用实例。
用于演示的图如下：

#include<iostream>
#define MaxVertexNum 6
#define MAXNUM 65535
using namespace std;
//抽象数据类型
typedef char vertextype;//顶点类型
//边结点类型
typedef struct edge
{
    int mark;
    int no;
    struct edge *next;
}edgetype;
//点结点类型
typedef struct
{
    int mark;
    vertextype vertex;
    edgetype *firstArc;
}vertexNode;
//图
typedef struct
{
    vertexNode vex[MaxVertexNum];
    int n,e;
}ALGraph;
ALGraph G;
ALGraph Tree;
typedef struct
{
    edgetype lowcost;//权值
    int nearvex;//顶点的序号
}node;
//标记顶点是否被访问过
int visited[MaxVertexNum];
//构造邻接表
void create(ALGraph &G)
{
    G.n=6;

    G.vex[0].vertex='A';
    G.vex[1].vertex='B';
    G.vex[2].vertex='C';
    G.vex[3].vertex='D';
    G.vex[4].vertex='E';
    G.vex[5].vertex='F';

    edgetype *e1=new edgetype;
    edgetype *e2=new edgetype;
    edgetype *e3=new edgetype;
    edgetype *e4=new edgetype;
    edgetype *e5=new edgetype;
    edgetype *e6=new edgetype;
    edgetype *e7=new edgetype;
    edgetype *e8=new edgetype;
    edgetype *e9=new edgetype;
    edgetype *e10=new edgetype;
    edgetype *e11=new edgetype;
    edgetype *e12=new edgetype;
    edgetype *e13=new edgetype;
    edgetype *e14=new edgetype;
    edgetype *e15=new edgetype;
    edgetype *e16=new edgetype;
    edgetype *e17=new edgetype;
    edgetype *e18=new edgetype;

    e1->no=e2->no=532;
    e3->no=e4->no=345;
    e5->no=e6->no=548;
    e7->no=e8->no=200;
    e9->no=e10->no=360;
    e11->no=e12->no=467;
    e13->no=e14->no=245;
    e15->no=e16->no=320;
    e17->no=e18->no=320;

    e1->mark=1;
    e2->mark=2;
    e3->mark=3;
    e4->mark=4;
    e5->mark=5;
    e6->mark=6;
    e7->mark=7;
    e8->mark=8;
    e9->mark=9;
    e10->mark=10;
    e11->mark=11;
    e12->mark=12;


    G.vex[0].firstArc=e1;
    e1->next=e3;
    e3->next=NULL;

    G.vex[1].firstArc=e2;
    e2->next=e7;
    e7->next=e5;
    e5->next=NULL;

    G.vex[2].firstArc=e4;
    e4->next=e8;
    e8->next=e9;
    e9->next=e11;
    e11->next=NULL;

    G.vex[3].firstArc=e6;
    e6->next=e10;
    e10->next=e13;
    e13->next=e15;
    e15->next=NULL;

    G.vex[4].firstArc=e12;
    e12->next=e14;
    e14->next=e17;
    e17->next=NULL;

    G.vex[5].firstArc=e16;
    e16->next=e17;
    e17->next=NULL;
}
void PrimMST(ALGraph &G,int k)
{
    edgetype *p;
    int i,j;
    for(i=0;i<G.n;i++)
        visited[i]=0;
    visited[k]=1;
    p=G.vex[k].firstArc;
    while(p!=NULL)
    {
        int min=p->no;
        int vex=p->mark;
        if(p->no<min)
        {
            min=p->no;
            vex=p->mark;
        }
        p=p->next;
    }
    cout<<p->no<<" "<<p->mark<<endl;
}
int main()
{
    create(G);
    PrimMST(G,0);
    return 0;
}