prim和kruskal算法c++

Prim's算法和Kruskal算法都是图论中用于寻找最小生成树（Minimum Spanning Tree, MST）的经典算法。

**Prim's算法**是一种贪心算法，从一个初始顶点开始，每次选择当前未连接到已选择边集合的节点中距离最近的一个，将其加入并更新最小生成树。这个过程会一直持续直到所有的顶点都被包含。在C++中，可以使用优先队列（如`std::priority_queue`）来存储未加入的边，并按权重排序。

以下是C++实现Prim's算法的基本步骤：
1. 初始化：创建一个集合（通常用邻接矩阵表示），并选取任意一个顶点作为起点。
2. 将起点的所有边添加到优先队列中，按照权重从小到大排序。
3. 当优先队列非空时，取出最小权值边，检查这条边是否将当前生成树扩大到新的顶点，如果是，则添加这条边及其端点，更新优先队列。
4. 重复步骤3，直到所有顶点都在生成树内。

**Kruskal's算法**则采用了分治的思想，它将图看作是一系列边，每次从未形成环的边中选取权值最小的一条加入结果中，直到形成一棵连通树。在C++中，可以使用并查集数据结构来跟踪边的独立性。

以下是C++实现Kruskal's算法的关键部分：
1. 对所有边进行排序，依据边的权值从小到大。
2. 使用并查集维护各个顶点所在的集合。
3. 遍历排序后的边，对于每一条边，如果它的两个端点不在同一个集合里（即它们代表的是两个独立的子图），就合并这两个集合并将该边加入结果中。
4. 重复步骤3，直到添加了(n-1)条边，其中n为顶点数，此时形成了最小生成树。