贪心算法是一种逐步构建解决方案的方法，每一步都选择当前状态下最优的局部选择，期望通过这些局部最优选择达到全局最优解。在图论问题中，贪心算法因其高效性和直观性而得到了广泛应用。
最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题，目标是在一个加权无向连通图中找到一棵包含所有顶点的树，使得这棵树的边权重之和最小。贪心算法中的普里姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）是求解MST问题的经典方法。
普里姆算法从图的任意一个顶点开始，逐步扩展生成树，每一步都选择一条连接生成树中顶点与未加入生成树顶点之间权重最小的边。其伪代码如下：
function Prim(Graph):
let mstSet[] be a boolean array of size V, initialized as false
let key[] be an array to store constructed MST's edge weight, initialized as INFINITE
let parent[] be an array to store constructed MST's edge, initialized as -1
key[0] = 0 // Start from the first vertex
for count from 0 to V-1:
// Pick the minimum key vertex not yet included in MST Set
u = vertex with min key value, that is not yet included in mstSet
// Include the picked vertex in the MST Set
mstSet[u] = true
// Update key value and parent index of the adjacent vertices of the picked vertex
for each vertex v adjacent to u:
if mstSet[v] == false and Graph[u][v] < key[v]:
parent[v] = u
key[v] = Graph[u][v]
克鲁斯卡尔算法则基于边的权重，从小到大逐步选择边，并使用并查集（Union-Find）来确保加入的边不会形成环。其伪代码如下：
function Kruskal(Graph):
let result[] be the resultant MST
let sorted_edges be all the edges of graph G sorted by weight in non-decreasing order
let parent[] be an array to use union-find subset
for each edge (u, v) in sorted_edges:
if find(parent, u) != find(parent, v):
result.add((u, v))
union(parent, u, v)
function find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])
function union(parent, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
parent[rootX] = rootY
贪心算法在求解最短路径问题时，以迪杰斯特拉算法（Dijkstra's Algorithm）为代表。该算法适用于加权有向图，其中所有边的权重非负。迪杰斯特拉算法通过每次选择当前最短路径未处理的顶点中距离源点最近的顶点，逐步更新其他顶点到源点的最短路径。
其伪代码如下：
function Dijkstra(Graph, src):
let dist[] be an array of minimum distances initialized to INFINITE and dist[src] = 0
let sptSet[] be a boolean array indicating the shortest path tree set initialized as false
for count from 0 to V-1:
// Pick the minimum distance vertex not yet processed
u = vertex with min dist[], that is not yet included in sptSet
// Mark the picked vertex as processed
sptSet[u] = true
// Update dist value of the adjacent vertices of the picked vertex
for each vertex v adjacent to u:
if not sptSet[v] and Graph[u][v] and dist[u] != INFINITE and dist[u] + Graph[u][v] < dist[v]:
dist[v] = dist[u] + Graph[u][v]
贪心算法在图论问题中的高效应用，尤其是在求解最小生成树和最短路径问题时，展示了其独特的优势和实用性。通过逐步构建解决方案并选择当前状态下的最优局部选择，贪心算法能够在多项式时间内找到高质量的近似解或最优解。