CY-Left

基本功底

普鲁姆算法 c++ 实现

Prim 算法

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

#include <iostream>

using namespace std;

typedef char VerTexType;
typedef int ArcType;


#define MVNum 1000
#define MAXV 100
#define ErrorVex -5
/**
 * 应该得到的最短路径结构,应该是个结构体数组!
 **/
struct primRoute
{
    // 最小边的起始点
    VerTexType adjvex;
    // 最小边
    ArcType lowcost;
};

/**
 * 这张该死的邻接矩阵
 * typedef char VerTexType;
 **/
struct graph
{

    int edges[MAXV][MAXV];   /*邻接矩阵*/

    int vexnum,arcnum;     /*顶点数,弧数*/

    VerTexType vexs[MAXV];  /*存放顶点信息*/

};      /*图的邻接矩阵类型*/

/** 最短路径 **/
primRoute closedge[MVNum];

/** 图  **/
graph MGraph;


/** 单纯的初始化 **/
void initGraph()
{
    MGraph.vexnum = 6;
    MGraph.arcnum = 20;

    // init 边
    for(int i=0; i<6; i++)
    {
        MGraph.vexs[i] = 'a'+i;
    }

    // init weight
    MGraph.edges[0][2] = 1;
    MGraph.edges[3][5] = 2;
    MGraph.edges[1][4] = 3;
    MGraph.edges[2][5] = 4;
    MGraph.edges[0][3] = 5;
    MGraph.edges[1][2] = 5;
    MGraph.edges[2][3] = 5;
    MGraph.edges[0][1] = 6;
    MGraph.edges[2][4] = 6;
    MGraph.edges[4][5] = 6;

    MGraph.edges[2][0] = 1;
    MGraph.edges[5][3] = 2;
    MGraph.edges[4][1] = 3;
    MGraph.edges[5][2] = 4;
    MGraph.edges[3][0] = 5;
    MGraph.edges[2][1] = 5;
    MGraph.edges[3][2] = 5;
    MGraph.edges[1][0] = 6;
    MGraph.edges[4][2] = 6;
    MGraph.edges[5][4] = 6;

    cout<<"tree matrix:"<<endl;
    cout<<"\\ ";
    for(int i=0; i<MGraph.vexnum; i++)
        cout<<MGraph.vexs[i]<<" ";
    cout<<endl;

    for(int i=0; i<MGraph.vexnum; i++)
    {
        cout<<MGraph.vexs[i]<<" ";
        for(int j=0; j<MGraph.vexnum; j++)
            cout<<MGraph.edges[i][j]<<" ";
        cout<<endl;
    }
}

int LocateVex(char G[], char vex)
{
    for(int i=0; i<MGraph.vexnum; i++)
    {
        if(G[i]==vex)
            return i;
    }
    return ErrorVex;
}

int getMinPoint(char U[],int ULen)
{

    int distance = INT_MAX;
    int kk = -2;
    for(int i=0; i<ULen; i++){
        int indexU = LocateVex(MGraph.vexs, U[i]);
        for(int j=0; j<MGraph.vexnum; j++)
        {
            if(MGraph.edges[indexU][j] == 0){continue;}

            // 查重
            int stat = 1;
            for(int m=0; m<ULen; m++) {
                if(MGraph.vexs[j]==U[m]) {stat = 0;break;}
            }
            if(stat == 0) {continue;}

            if(MGraph.edges[indexU][j] < distance && MGraph.edges[indexU][j] != 0)
            {
                distance = MGraph.edges[indexU][j];
                kk = j;
            }
        }
    }
    /** 返回下一个最短点的位置坐标 **/
    return kk;
}

/**
 * prim core algorithm
 **/
void prim(VerTexType u = 'a')
{
    /** 一、首先,获得一张初始化的图  **/
    initGraph();

    /** 二、初始化普里姆的定点结合 U 以及 TE (边集)  **/
    // kk 此时代表起点 a
    int kk = LocateVex(MGraph.vexs, u);

    /** 定点集合 U,开始只存放起点  **/
    char U[MGraph.vexnum]; U[0] = u;int ULen = 1;

    /** 边集 TE ,这里命名为 closedge ,开始为空  **/
    primRoute closedge[MGraph.vexnum-1]; // 最短路径

    /** 这一层遍历顶点集合 U 中的所有最短路径  **/
    for(int h=0; h<MGraph.vexnum-1; h++)
    {
        int distance = INT_MAX;

        /** 获取距离 a 最近的点,并存给 kk **/
        for(int i=0; i<ULen; i++){
            int indexU = LocateVex(MGraph.vexs, U[i]);
            for(int j=0; j<MGraph.vexnum; j++)
            {
                if(MGraph.edges[indexU][j] == 0){continue;}

                // 查重
                int stat = 1;
                for(int m=0; m<ULen; m++) {
                    if(MGraph.vexs[j]==U[m]) {stat = 0;break;}
                }
                if(stat == 0) {continue;}

                if(MGraph.edges[indexU][j] < distance && MGraph.edges[indexU][j] != 0)
                {
                    distance = MGraph.edges[indexU][j];
                    kk = j;
                }
            }
        }

        closedge[h] = {MGraph.vexs[kk], distance}; // 边, 边长
        U[h+1] = MGraph.vexs[kk];
        ULen++;

        cout<<endl<<"最新延伸到的点:"<<MGraph.vexs[kk]<<endl;
        for(int i=0;i<ULen;i++) cout<<U[i]<<" ";
        cout<<endl;
    }

    /** closedge 结果 **/
    for(int i=0;i<MGraph.vexnum-1;i++){
        cout<<closedge[i].lowcost<<"->["<<closedge[i].adjvex<<"]"<<" ";
    }
}

/**
 * main function
 **/
int main()
{
    prim();

    return 0;
}

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=715