在图论中，最小生成树（Minimum Spanning Tree, MST）问题是一个经典而重要的问题。它要求在一个带权无向连通图中，找到一棵包含所有顶点且边权之和最小的生成树。贪心算法是解决此类问题的一种有效方法，其中最著名的算法包括Prim算法和Kruskal算法。
Prim算法是一种贪心算法，用于从给定的加权无向图中找到一个最小生成树。其工作原理是从图中的某一顶点开始，逐步扩展生成树，每次选择连接生成树顶点集合与不在生成树中的顶点集合之间权重最小的边。
具体步骤如下：
下面是Prim算法的伪代码：
function Prim(Graph):
// 初始化
mstSet = [] // 存储最小生成树中的顶点
key = [] // 存储顶点与最小生成树中顶点集合的最小边权重
parent = [] // 存储构建最小生成树的父节点信息
// 初始化所有键值为无穷大
for each vertex v in Graph:
key[v] = INFINITY
parent[v] = NIL
// 将第一个顶点的键值设为0，使其成为最小生成树的第一个顶点
key[0] = 0
parent[0] = -1 // 第一个节点是根节点
// 构建最小生成树的集合
for count from 0 to V-1:
// 从未处理顶点集合中挑选键值最小的顶点u
u = EXTRACT-MIN(key, mstSet)
// 将选中的顶点u加入最小生成树集合
mstSet.add(u)
// 更新u的邻接顶点的键值及父节点信息
for each vertex v adjacent to u:
if v not in mstSet and Graph[u][v] < key[v]:
parent[v] = u
key[v] = Graph[u][v]
return parent, key
Kruskal算法是另一种解决最小生成树问题的贪心算法。它的核心思想是从小到大依次选择图中的边，并保证不会形成环，直到构成一棵包含所有顶点的生成树。
具体步骤如下：
下面是Kruskal算法的伪代码：
function Kruskal(Graph):
// 初始化
mst = [] // 存储最小生成树的边
parent = [] // 存储构建最小生成树的父节点信息
// 初始化并查集
for each vertex v:
parent[v] = v
rank[v] = 0
// 将边按权重排序
edges = SORT(Graph.edges, by weight)
for each edge (u, v) in edges:
// 如果u和v不在同一集合中，合并它们的集合
if FIND(parent, u) != FIND(parent, v):
UNION(parent, rank, u, v)
mst.add((u, v))
return mst
注意：上述伪代码中的并查集部分（FIND和UNION操作）是实现Kruskal算法的关键。
贪心算法在图论中的最小生成树问题应用中展现出了极高的效率。Prim算法和Kruskal算法各有优劣，选择哪种算法通常取决于图的具体特性和应用需求。Prim算法更适合稠密图，而Kruskal算法更适合稀疏图。