最小生成树笔记

两种常用的最小生成树算法：

①普里姆算法（Prim，时间复杂度O( n^2 )）----引入一个辅助数组，便巧妙实现之

②克鲁斯卡尔算法（ Kruskal ，时间复杂度O( e log e)

Prim算法是根据点找边，适合稠密图。Kruskal算法一直都是找最小边，适合稀疏图。

Prim算法的伪代码：

void MiniSpanTree_PRIM( MGraph G, VertexType u)
{
	/*
	struct
	{VertexType adjvex;
	VRTYPE lowcost;
	}closedge[G.vexnum]
	*/

	k= locateVex( G, u);
	for ( int j = 0; j < G.vexnum; j++)
		if ( j != k) closedge[j] = { u , G.arcs[k][j].adj};
	
	closedge[k].lowcost = 0;

	for ( int i = 1; i < G.vexnum; i++)
	{
		k = mininum( closedge);
		printf( closedge[k].adjvex, G.vexs[k]);
		closedge[k].lowcost = 0;

		for ( j = 0; j < G.vexnum; j++)
			if( G.arcs[k][j].adj < closedge[j].lowcost)
				closedge[j] ={G.vexs[k], G.arcs[k][j].adj };
	}
}