最小生成树，普利姆算法．

简述算法:

　　先初始化一棵只有一个顶点的树，以这一顶点开始，找到它的最小权值，将这条边上的令一个顶点添加到树中

　　再从这棵树中的所有顶点中找到一个最小权值（而且权值的另一顶点不属于这棵树）

　　重复上一步．直到所有顶点并入树中．

图示：

注：以a点开始，最小权值为１，另一顶点是ｃ，将ｃ加入到最小生成树中．树中　ａ－ｃ

在最小生成树中的顶点找到一个权值最小且另一顶点不在树中的，最小权值是４，另一个顶点是ｆ，将ｆ并入树中，　ａ－ｃ－ｆ

重复上一步骤，ａ－ｃ－ｆ－ｄ，　ａ－ｃ－ｆ－ｄ－ｂ，　ａ－ｃ－ｆ－ｄ－ｂ－ｅ．

邻接矩阵的实现

我又构建了一个邻接矩阵（prim_tree)，将我们求出的最小生成树写入其中．

我们还需要一个visited数组，来确定一个顶点是否已被纳入最小生成树中．

１）初始化，visited数组，prim_tree节点信息，矩阵．１－１１，４１－５５行

２）将一个顶点并入树（prim_tree）中．以这个顶点开始，进行遍历寻找最小权值．

　　这里用了三层循环嵌套．

　　　　ｉ这一层的作用是遍历图的节点信息，我们要将所有节点都纳入树中．

　　　　ｊ这一层的作用是遍历树的节点信息．（我们是通过visited数组来确定一个节点是否属于最小生成树的，１９行，ｉｆ的作用）

　　　　ｋ这一层的作用是在ｊ节点所在所在矩阵的行中找到最小权值．

　（注：ｊ和ｋ配合，找到树中的最小权值（最小权值的另一个节点没有被纳入树中，２３行ｉｆ的作用）．ｊ查找的节点信息的下标，但矩阵是正方形的，所以ｊ既是节点信息的下标，又是该节点在矩阵中的列位置．而ｋ则在ｊ这一列查找最小权值．当ｊ将树遍历一遍，这时会找到一个最小权值，这个最小权值的另一个顶点就是我们将要纳入树中的节点．）

３）将上面获得的信息写入树中．（写入时也要判断该节点是否已被纳入树中．没有纳入树中的节点才会将其纳入树中．）

1 //最小生成树prim算法 2 static void init_prim(Graph * graph, Graph * prim_tree); 3 void Prim(Graph * graph, Graph * prim_tree) 4 { 5     bool visited[graph->vertexs]; 6     int i, j, k, h; 7     int power, power_j, power_k; 8  9     for ( i = 0; i < graph->vertexs; i++ )10         visited[i] = false;11     init_prim(graph, prim_tree);12 13     visited[0] = true;14     for ( i = 0; i < graph->vertexs; i++ )15     {16         power = MAX_VALUE;17         for ( j = 0; j < graph->vertexs; j++ )18         {19             if ( visited[j] )20             {21                 for ( k = 0; k < graph->vertexs; k++ )22                 {23                     if ( power > graph->arcs[j][k] && !visited[k] )24                     {25                         power = graph->arcs[j][k];26                         power_j = j;27                         power_k = k;28                     }29                 }30             }31         }32         //min power33         if ( !visited[power_k] )34         {35             visited[power_k] = true;36             prim_tree->arcs[power_j][power_k] = power;37         }38     }39 }40 41 static void init_prim(Graph * graph, Graph * prim_tree)42 {43     int i, j;44 45     prim_tree->vertexs = graph->vertexs;46     for ( i = 0; i < prim_tree->vertexs; i++ )//初始化节点47         prim_tree->vertex[i] = graph->vertex[i];48     for ( i = 0 ; i < prim_tree->vertexs; i++ )//初始化矩阵49     {50         for ( j = 0; j < prim_tree->vertexs; j++ )51         {52             prim_tree->arcs[i][j] = MAX_VALUE;53         }54     }55 }

上述代码适用于连通图．

如果想运行这个程序，到http://www.cnblogs.com/ITgaozy/p/5187483.html找源码，将上面的代码粘到里面就可以了．

 

邻接表的实现

算法和矩阵一样，只是由于数据结构不同，在代码上有些差别．

static void init_prim(Graph * graph, Graph * prim_tree);void g_prim(Graph * graph, Graph * prim_tree){    bool visited[graph->vertexs];    int i, j, k;    int power, pos;    Arc_node * tmp;    for ( i = 0; i < graph->vertexs; i++ )        visited[i] = false;    init_prim(graph, prim_tree);    visited[0] = true;    for ( i = 0; i < graph->vertexs; i++ )    {        power = INT_MAX;//limits.h        for ( j = 0; j < graph->vertexs; j++ )        {            if ( visited[j] )            {                tmp = graph->adjlist[j].next;                while ( tmp != NULL )                {                    if ( power > tmp->distance && !visited[tmp->pos] )                    {                        power = tmp->distance;                        pos = tmp->pos;                        k = j;                    }                    tmp = tmp->next;                }            }        }        if ( !visited[pos] )        {            if ( prim_tree->adjlist[k].next == NULL )            {                prim_tree->adjlist[k].next = make_node(pos, power);            }            else            {                tmp = prim_tree->adjlist[k].next;                while ( tmp->next != NULL )                    tmp = tmp->next;                tmp->next = make_node(pos, power);            }            visited[pos] = true;        }    }}static void init_prim(Graph * graph, Graph * prim_tree){    int i;    for ( i = 0; i < graph->vertexs; i++ )    {        prim_tree->adjlist[i].info = graph->adjlist[i].info;        prim_tree->adjlist[i].next = NULL;    }    prim_tree->vertexs = graph->vertexs;}

到http://www.cnblogs.com/ITgaozy/p/5187526.html里找到源码，将上述代码粘到源码中，就可以了．

由于本人水平有限，不足之处还望大家不吝指教．