最小路径(prim)算法

#include <stdio.h>
#include <stdlib.h>

/* 最小路径算法 --》prim算法 */

#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, MV, 16, 21},
    {MV, MV, MV, 20, 0, 26, MV, 7, MV},
    {11, MV, MV, MV, 26, 0, 17, MV, MV},
    {MV, 16, MV, MV, MV, 17, 0, 19, MV},
    {MV, MV, MV, 16, 7, MV, 19, 0, MV},
    {MV, 12, 8, 21, MV, MV, MV, MV, 0},
};
//sv开始
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];
            P[i] = sv;  //记录边数组
            Mark[i] = 0;//初始化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) )
                {
                    min = Cost[j];
                    index = j;
                }
            }
            //成立 找到最小值 打印
            if( index > -1 )
            {
                Mark[index] = 1;
                
                printf("(%d, %d, %d) ", P[index], index, Cost[index]);
            }
            //查看是否有最小的边存在
            for(j=0; j<VNUM; j++)
            {
            //刚刚被标记的边  
                if( !Mark[j] && (Matrix[index][j] < Cost[j]) )
                {
                    Cost[j]  = Matrix[index][j];
                    P[j] = index;
                }
            }
        }
    }
}

int main(int argc, char *argv[])
{
      Prim(0);
    
    return 0;
}

说明：

1.Prim算法是针对顶点展开的， 适合于边的数量较 适合于边的数量较多的情况。

2.Kruskal算法是针对边展开的， 适合于边的数量较 适合于边的数量较少的情况。