最小生成树之普里姆算法_已知一带权连通图如图所示。根据prim算法求出其所有可能的最小生成树

• 方案二：如下图所示，所需成本为10+12+8+11+17+19+16+7=100

• 方案三：如下图所示，所需成本为8+12+16+10+11+19+16+7=99

• 第一步：选择一个出发点，比如V0，将其背景色由白色变成黑色：

• 第二步：把结点V0与相邻结点间的边变成紫色：

• 第三步：在紫色的边中选取一条权值最小的边，将此边变成红色，相邻结点变色黑色：

• 第四步：将黑色顶点与白色顶点间的边变成紫色，若一个白色顶点与多个黑色顶点有边相连，则选取权值最小的边变成紫色，其它的边变成灰色，表示不考虑

• 第五步：在紫色边中选择一条权值最小的边，将此边变成红色，相邻结点变成黑色：

• 第六步：将黑色顶点与白色顶点间的边变成紫色，若一个白色顶点与多个黑色顶点有边相连，则选取权值最小的边变成紫色，其它的边变成灰色，表示不考虑

• 第七步：在紫色边中选择一条权值最小的边，将此边变成红色，相邻顶点变成黑色：

• 第八步：在紫色边中选择一条权值最小的边，将此边变成红色，相邻顶点变成黑色：

• 第九步：将黑色顶点与白色顶点间的边变成紫色，若一个白色顶点与多个黑色顶点有边相连，则选取权值最小的边变成紫色，其它的边变成灰色，表示不考虑：
  

• 第十步：在紫色边中选择一条权值最小的边，将此边变成红色，相邻顶点变成黑色。普里姆算法构造最小生成树结束，黑色顶点和红色边组成的树就是最小生成树：

/*********************************************************************/
/**            最小生成树之普里姆算法(邻接矩阵存储图)                   **/
/*********************************************************************/
 
#include <stdio.h>
 
#define GRAPH_MAX_VERTEX_SIZE 100           // 最大顶点数
#define INFINITY 65535                      // 用65535来代表∞，在这里代表村庄之间没有可达路径
 
typedef char VertexType;     // 顶点类型
typedef int EdgeType;        // 边上的权值类型
 
typedef struct Graph
{
	VertexType vexs[GRAPH_MAX_VERTEX_SIZE];           // 顶点表
	EdgeType arc[GRAPH_MAX_VERTEX_SIZE][GRAPH_MAX_VERTEX_SIZE];      // 邻接矩阵
	int numVertexs, numEdges;            // 图中当前的顶点数和边数
}Graph;
 
/**
 * 建立无向网图的邻接矩阵表示
 * @param graph：指向图结构的指针
 */
void CreateGraph(Graph *graph)
{
	int i, j, k, w;
 
	printf("输入顶点数和边数，分别用空格分隔:");
	scanf("%d %d", &(graph->numVertexs), &(graph->numEdges));          // 接收输入的顶点数和边数
 
	for(i = 0; i < graph->numVertexs; i++)                             // 读入顶点信息,建立顶点表
	{
	    printf("输入第%d个顶点信息：", i + 1);
        fflush(stdin);                                                 // 清空键盘输入缓冲区
		scanf("%c", &(graph->vexs[i]));
	}
 
	for(i = 0; i < graph->numVertexs; i++)
	{
		for(j = 0; j < graph->numVertexs; j++)
		{
			graph->arc[i][j] = INFINITY;	                           // 邻接矩阵初始化
		}
	}
 
	for(k = 0; k < graph->numEdges; k++)                               // 读入numEdges条边，建立邻接矩阵
	{
		printf("输入边(vi,vj)上的下标i，下标j和权w，分别用空格分隔：");
		fflush(stdin);                                                 // 清空键盘输入缓冲区
		scanf("%d %d %d", &i, &j, &w);
		graph->arc[i][j] = w;
		graph->arc[j][i] = graph->arc[i][j];                           // 因为是无向图，矩阵对称
	}
}
 
 
/**
 * 普里姆算法生成最小生成树
 */
void Prim(Graph graph)
{
    int min, i, j, k;
 
    int adjvex[GRAPH_MAX_VERTEX_SIZE];   // 保存相关顶点下标
    int lowcost[GRAPH_MAX_VERTEX_SIZE];  // 保存相关顶点之间边的权值(成本)
 
    adjvex[0] = 0;                       // V0第一个加入
    lowcost[0] = 0;                      // V0作为最小生成树的根开始遍历，权值为0
 
    // 初始化
    for(i = 1; i < graph.numVertexs; i++)
    {
        lowcost[i] = graph.arc[0][i];    // 将邻接矩阵第0行所有权值加入数组中
        adjvex[i] = 0;                   // 初始化全部先为V0的下标
    }
 
    // 构造最小生成树
    for(i = 1; i < graph.numVertexs; i++)
    {
        min = INFINITY;                  // 初始化最小权值为65535等不可能的数值
        j = 1;
        k = 0;
 
        // 遍历全部顶点
        while(j < graph.numVertexs)
        {
            // 找出lowcost数组已存储的最小权值
            if(lowcost[j] != 0 && lowcost[j] < min)
            {
                min = lowcost[j];
                k = j;                   // 将发现的最小权值的下标赋值给k
            }
            j++;
        }
 
 
        // 打印当前顶点边中权值最小的边
        printf("(%d, %d)", adjvex[k], k);
        lowcost[k] = 0;                     // 将当前顶点的权值设为0，表示此顶点已完成任务，进入下一个顶点的遍历
 
        // 邻接矩阵k行逐个遍历全部顶点
        for(j = 1; j <graph.numVertexs; j++)
        {
            if(lowcost[j] != 0 && graph.arc[k][j] < lowcost[j])
            {
                lowcost[j] = graph.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
}
 
int main()
{
    Graph graph;
 
    CreateGraph(&graph);
    Prim(graph);
    return 0;
}