PRIM算法
实现思想
准备工作
1. 在图当中选择一个顶点作为起点。
2. 建立一个dis数组,dis[i]代表了i号顶点加入生成树的最短距离。
3. 建立一个vis数组,vis[i]表示i号顶点是否已经被访问过。
4. 将起点距离生成树的最短距离更新为0,即dis[start] = 0
算法运行
根据贪心思想,每一次挑选一个距离生成树最近的顶点,加入生成树,并更新距离生成树的最短距离。
1. 找到距离生成树最近的顶点,加入生成树。
2. 通过新加入生成树顶点的相邻顶点,更新其相邻顶点的到达生成树的最短距离。
3. 重复步骤1和步骤2,直到生成树的顶点数等于图的顶点数。
代码实现