一步一步学数据结构之n--n（Prim算法）

在这里说下最小连通网的Prim算法：

而Kruskal算法，http://blog.csdn.net/nethanhan/article/details/10050735有介绍，大家可以去看下!

Prim算法代码:

#include <stdio.h>

#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

#define VNUM 9

#define MV 65536

int P[VNUM];//记录边

int Cost[VNUM];//存储每一条边所要耗费的成本

int Mark[VNUM];//标记顶点

int Matrix[VNUM][VNUM] =

{//图

    {0, 10, MV, MV, MV, 11, MV, MV, MV},

    {10, 0, 18, MV, MV, MV, 16, MV, 12},

    {MV, 18, 0, 22, MV, MV, MV, MV, 8},

    {MV, MV, 22, 0, 20, MV, 24, 16, 21},

    {MV, MV, MV, 20, 0, 26, MV, 7, MV},

    {11, MV, MV, MV, 26, 0, 17, MV, MV},

    {MV, 16, MV, 24, MV, 17, 0, 19, MV},

    {MV, MV, MV, 16, 7, MV, 19, 0, MV},

    {MV, 12, 8, 21, MV, MV, MV, MV, 0},

};

void Prim(int sv) // O(n*n)

{

    int i = 0;//循环变量

    int j = 0;//循环变量

    if( (0 <= sv) && (sv < VNUM) )

    {

        for(i=0; i<VNUM; i++)

        {

            Cost[i] = Matrix[sv][i];//初始动点与其它顶点相连边的权值赋给cost数组

            P[i] = sv;//保存边

            Mark[i] = 0;//初始化标记

        }

        Mark[sv] = 1;//标记顶点 

        for(i=0; i<VNUM; i++)

        {

            int min = MV;

            int index = -1;

            for(j=0; j<VNUM; j++)

            {//挑选最小权值的边

                if( !Mark[j] && (Cost[j] < min) )

                {//挑选完毕以后，index保存另一个顶点

                    min = Cost[j];

                    index = j;

                }

            }

            if( index > -1 )

            {//如果为真，则说明照到最小值

                Mark[index] = 1;

                printf("(%d, %d, %d)\n", P[index], index, Cost[index]);

            }

            for(j=0; j<VNUM; j++)

            {//从刚才被标记的顶点作为起始顶点

                if( !Mark[j] && (Matrix[index][j] < Cost[j]) )

                {//然后从新的起始顶点与其他顶点（非标记顶点）相连边的权值中寻找更小的，更新cost数组

                    Cost[j]  = Matrix[index][j];

                    P[j] = index;//如果有其它更小的，那么此边的起始顶点为P[i]，也就是index，权值保存在cost数组中

                }

            }

        }

    }

}

int main(int argc, char *argv[])

{

         Prim(0);

	return 0;

}

巴特西

一步一步学数据结构之n--n（Prim算法）

最新文章

热门文章