贪婪算法示例：最小生成树（Kruskal 算法）

Kruskal算法是一种用来找到加权无向图中最小生成树的贪心算法。最小生成树是指在一个加权无向图中，包含所有顶点且边的权重之和最小的树。

以下是Kruskal算法的步骤：

1. 将所有的边按照权重从小到大排序。
2. 初始化一个空的最小生成树。
3. 遍历排序后的边列表，对于每条边：
a. 如果这条边连接的两个顶点在最小生成树中尚未连接（即它们属于不同的连通分量），则添加这条边到最小生成树中。
b. 如果这条边连接的两个顶点已经在同一个连通分量中，则忽略这条边，继续检查下一条边。
4. 重复步骤3直到最小生成树中包含了所有顶点。

我们可以通过一个简单的例子来展示这个算法：

import java.util.Arrays;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Graph {
    private final int vertices;
    private Edge[] edgeArray;

    public Graph(int vertices, Edge[] edgeArray) {
        this.vertices = vertices;
        this.edgeArray = edgeArray;
    }

    public int find(int parent[], int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }

    public void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        if (xset != yset) {
            parent[xset] = yset;
        }
    }

    public void kruskalMST() {
        Edge result[] = new Edge[vertices];
        int e = 0; // Result array index
        int i = 0; // Index in sorted edgeArray

        // Step 1: Sort all edges in non-decreasing order of their weight
        Arrays.sort(edgeArray);

        // Allocate memory for creating V subsets
        int parent[] = new int[vertices];
        for (int v = 0; v < vertices; ++v) {
            parent[v] = -1
        while (e < vertices - 1 && i < edgeArray.length) {
            Edge next_edge = edgeArray[i++];

            int x = find(parent, next_edge.src);
            int y = find(parent, next_edge.dest);

            // If including this edge doesn't cause cycle, include it in result
            // and do a union of two sets.
            if (x != y) {
                result[e++] = next_edge;
                union(parent, x, y);
            }
            // Else discard the next_edge
        }

        // Print the constructed MST
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }
}

public class KruskalExample {
    public static void main(String[] args) {
        /* Let us create the following weighted graph
             10
        0--------1
        | \     / |\
        6  |8/6 | 8\
        | \ / | 8  | 2
        2--------3
             4           */
        int V = 4;  // Number of vertices in graph
        int E = 5;  // Number of edges in graph
        Edge[] edgeArray = { new Edge(0, 1, 10), new Edge(0, 2, 6), new Edge(0, 3, 5),
                              new Edge(1, 3, 15), new Edge(2, 3, 4) };

        Graph graph = new Graph(V, edgeArray);
        graph.kruskalMST();
    }
}

这段代码定义了一个图，并使用Kruskal算法找到它的最小生成树。图中的顶点通过一个Edge数组表示，每条边包含起点、终点和权重。通过排序和并查集的方式，我们能够构造出最小生成树并输出结果。