最小生成树(Minimum Spanning Tree,MST)是图论中的一个重要概念,它指的是在一个加权无向图中,包含所有顶点且边权总和最小的树。最小生成树在许多领域都有应用,如网络优化、路径规划等。普里姆算法是求解最小生成树的经典算法之一,它以其高效和易于实现的特点在计算机科学中得到广泛应用。
普里姆算法的基本思想
普里姆算法的基本思想是从图中选择一个初始顶点作为生成树的一部分,然后逐步添加边,每次添加的边都是当前未被选中顶点与已选顶点集合之间权值最小的边。这个过程持续进行,直到所有顶点都包含在生成树内。
普里姆算法的步骤
初始化
:设S为一个空集合,V为所有顶点集合,初始时S仅包含一个顶点(例如V0),其余顶点距离设为无穷大(记作INF)。
选择最小边
:在V-V(V与V的差集)中找到与S中顶点相连的边中权值最小的一条,这条边的起始端点u被添加到S中。
更新距离
:对于S的新成员u,更新它与其他未加入S的顶点v之间的最短距离。这一步可能涉及到邻接矩阵或邻接表的查找操作。
重复步骤2和3
,直到S包含所有顶点。此时,S中的边就构成了最小生成树。
普里姆算法的实现
普里姆算法可以通过邻接矩阵或邻接表来实现。以下是一个使用邻接矩阵实现的普里姆算法的示例代码:
#include
#include
#include
using namespace std;
const int MAXVEX = 100;
int graph[MAXVEX][MAXVEX]; // 邻接矩阵
int n; // 顶点数量
void Prim(int v) {
vector
vector
key[v] = 0;
for (int i = 0; i < n; ++i) { int u = -1, min = INT_MAX; for (int j = 0; j < n; ++j) { if (!inTree[j] && graph[v][j] < min) { min = graph[v][j]; u = j; } } if (u == -1) break; inTree[u] = true; key[u] = min; for (int j = 0; j < n; ++j) { if (!inTree[j] && graph[u][j] < key[j]) { key[j] = graph[u][j]; } } } // 输出最小生成树 for (int i = 0; i < n; ++i) { if (key[i] != INT_MAX) { cout << "边(" << i << ", " << v << ") 权重 " << key[i] << endl; } } } int main() { // 构建邻接矩阵 n = 4; graph[0][0] = 0; graph[0][1] = 2; graph[0][2] = 3; graph[0][3] = 6; graph[1][0] = 2; graph[1][1] = 0; graph[1][2] = 1; graph[1][3] = 4; graph[2][0] = 3; graph[2][1] = 1; graph[2][2] = 0; graph[2][3] = 2; graph[3][0] = 6; graph[3][1] = 4; graph[3][2] = 2; graph[3][3] = 0; Prim(0); // 从顶点0开始构建最小生成树 return 0; } 普里姆算法的时间复杂度 普里姆算法的时间复杂度为O(n^2),适用于稠密图。当使用优先队列优化时,时间复杂度可降至O(E log V),其中E是边的数量,V是顶点的数量。 总结 普里姆算法是一种高效且易于实现的最小生成树求解算法。它通过逐步构建生成树,并选择权值最小的边来确保最终生成的树是包含所有顶点且边权总和最小的树。在实际应用中,普里姆算法在许多领域都发挥着重要作用。