数据结构——最小生成树之prime算法(与最短路径之迪杰斯特拉算法很像)

最小生成树之prime算法

***最小生成树：一个连通图的生成树中，所有边的权值加起来最小的生成树；称为最小生成树；

【简介】：Prime算法可在加权连通图里搜索最小生成树。即：所有边的权值之和为最小。

Prime算法是图论中求最小生成树的一种算法，与之类似的算法还有Kruskal算法；

区别：

Prime算法适合边多定点少的图；

Dijkstra算法适合边少定点多的图；

1.1 存图方式

要求最小生成树，当然首先要把图存进一个东西中，这样才能图对进行搜索操作。

1.邻接矩阵

存图思想：用一个矩阵来记录一个图，矩阵第 i 行第 j 列的值就表示顶点 i 到顶点 j 的权值

int matrix[MAX][MAX]={0};