三十功名尘与土，八千里路云和月。莫等闲，白了少年头，空悲切！

                                                                ---《满江红》岳飞

目录

前言

一、prim算法是什么？

二、使用步骤

1.核心思想

2.所有测试代码

总结

前言

一个连通图的生成树是一个极小的连通子图，它含有图中所有的顶点，但只有足以构成一棵树的

n-1条边。 定义：把构成联通网最小代价的生成树称为最小生成树。

一、prim算法是什么？

       普利姆(Prim)算法是一种求最小生成树的算法，时间复杂度为O(n2).。

        另外还有克鲁斯卡尔(Kruskal)算法。

二、使用步骤

1.核心思想

类似于贪心思想：即每步都寻求最优解（最短路），直到遍历所有顶点。

详细代码如下：

void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];	
	int lowcost[MAXVEX];
	lowcost[0] = 0;    
	adjvex[0] = 0;	

	for (i = 1; i < G.numVertexes; i++)
	{
		lowcost[i] = G.arc[0][i]; 
		adjvex[i] = 0;			
	}
	for (i = 1; i < G.numVertexes; i++)
	{
		min = GRAPH_INFINITY;	
		j = 1; k = 0;
		while (j 
2.所有测试代码 
代码如下：
 
#include 
using namespace std;
#define MAXVEX 100
#define GRAPH_INFINITY 65535
typedef struct {
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph* G)
{
	int i, j;
	
	G->numEdges = 15;
	G->numVertexes = 9;
	
	for (i = 0; i < G->numVertexes; i++)
	{
		for (j = 0; j < G->numVertexes; j++)
		{
			if (i == j)
				G->arc[i][j] = 0;
			else
				G->arc[i][j] = GRAPH_INFINITY;
		}
	}
	G->arc[0][1] = 10;
	G->arc[0][5] = 11;
	G->arc[1][2] = 18;
	G->arc[1][8] = 12;
	G->arc[1][6] = 16;
	G->arc[2][8] = 8;
	G->arc[2][3] = 22;
	G->arc[3][8] = 21;
	G->arc[3][6] = 24;
	G->arc[3][7] = 16;
	G->arc[3][4] = 20;
	G->arc[4][7] = 7;
	G->arc[4][5] = 26;
	G->arc[5][6] = 17;
	G->arc[6][7] = 19;
	for (i = 0; i < G->numVertexes; i++)
	{
		for (j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] = G->arc[i][j];
		}
	}
}
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];	
	int lowcost[MAXVEX];
	lowcost[0] = 0;    
	adjvex[0] = 0;	

	for (i = 1; i < G.numVertexes; i++)
	{
		lowcost[i] = G.arc[0][i]; 
		adjvex[i] = 0;			
	}
	for (i = 1; i < G.numVertexes; i++)
	{
		min = GRAPH_INFINITY;	
		j = 1; k = 0;
		while (j 
 

总结 
以上就是今天要讲的内容，本文仅仅简单介绍了prim算法的使用，而prim算法的掌握仍需要多做相关例题。