图的最小生成树怎么化

### 图的最小生成树算法

#### Prim 算法实现

Prim 算法是一种用于寻找加权连通图中的最小生成树的经典算法。该算法通过逐步扩展一棵正在生长的树来构建最终的最小生成树，每次迭代都会选择一个与当前树相连且权重最小的边。

#include <iostream>
#include <climits>

using namespace std;

#define V 5

// 找到不在MST集合中的顶点u,使得key[u]最小
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
  
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
  
    return min_index;
}

void printMST(int parent[], int graph[V][V]) {
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << endl;
}

void primMST(int graph[V][V]) {
    int parent[V]; // 存储构造的MST
    int key[V];   // 使用于挑选最小权重边
    bool mstSet[V];  // 跟踪哪些节点已包含在MST中
  
    // 初始化所有的键值为无穷大，父指针为-1
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX, mstSet[i] = false;
    }
    
    // 始终从第一个顶点开始
    key[0] = 0;
    parent[0] = -1; 
  
    // MST有V-1条边
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        
        // 将选中的顶点加入MST集
        mstSet[u] = true;
        
        // 更新相邻顶点的关键字值
        for (int v = 0; v < V; v++)

          // 如果v未处理过、存在边(u,v)，则更新关键字
          if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
              parent[v] = u, key[v] = graph[u][v];
    }

    // 输出构造好的MST
    printMST(parent, graph);
}

此代码实现了Prim算法的核心逻辑[^1]。程序首先初始化所有顶点的距离为无限远，并设置起始顶点的距离为零；接着不断选取距离最近的一个尚未访问过的顶点作为新的起点，调整其邻居们的最短路径估计直到所有顶点都被纳入生成树为止。

#### Kruskal 算法概述

除了Prim算法之外，还有另一种常用的求解最小生成树的方法——Kruskal算法。这种方法不是像Prim那样维护一颗逐渐增长的树，而是直接考虑每一条可能成为部分解决方案的边，在不形成环路的前提下尽可能早地把它们添加进来。

对于给定的一组无向带权边E={e_1,e_2,...,e_m}，按照从小到大的顺序排列这些边之后依次考察每一个候选者e_i=(u,v,w)，如果连接这两个端点不会造成循环，则将其加入到当前的部分解答之中并继续检查下一个元素直至完成整个过程[^2]。