数据结构第15节 最小生成树

最小生成树（Minimum Spanning Tree, MST）是指在一个连通的带权无向图中，由所有顶点构成的一棵树，其所有的边的权重之和最小。最小生成树在实际中有许多应用，比如网络设计、城市规划中的电线或水管铺设等。

有两种著名的算法用于寻找最小生成树：Prim算法和Kruskal算法。

Prim算法：

Prim算法从图中的某个顶点开始，逐步将顶点加入到生成树中，每次选择一个能够连接已加入顶点集的未加入顶点的边，且这条边的权重是最小的。

案例分析：
假设我们有一个村庄网络，其中各个村庄通过道路相连，每条道路有不同的长度（权重）。我们的目标是建立一个覆盖所有村庄的网络，使得总的建设成本最低。

步骤：

1. 选择任意一个村庄作为起始点。
2. 在所有连接已选村庄和未选村庄的边中，选择权重最小的边。
3. 将这条边对应的未选村庄加入到已选村庄集中。
4. 重复步骤2和3，直到所有村庄都被加入。

Kruskal算法：

Kruskal算法则是先对所有边按照权重进行排序，然后从小到大选取边，只要这条边不会形成环路就将其加入到生成树中。

案例：
还是使用村庄网络的例子，但是这次我们并不关心从哪个村庄开始，而是直接考虑所有可能的连接方式。

步骤：

1. 将所有边按权重排序。
2. 初始化一个空的生成树。
3. 遍历排序后的边，对于每条边检查它两端的顶点是否已经在生成树中相连。
4. 如果顶点未相连，则将这条边加入生成树。
5. 重复步骤3和4，直到生成树包含了所有顶点。

Java代码示例（Prim算法）：

import java.util.*;

public class PrimMST {
    private final List<List<Edge>> graph;
    private boolean[] inMST;

    public PrimMST(List<List<Edge>> graph) {
        this.graph = graph;
        this.inMST = new boolean[graph.size()];
        Arrays.fill(inMST, false);
        this.computeMST();
    }

    private void computeMST() {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        inMST[0] = true; // Start from vertex 0.
        for (Edge edge : graph.get(0)) {
            pq.offer(edge);
        }

        while (!pq.isEmpty()) {
            Edge minEdge = pq.poll();
            int to = minEdge.to;
            if (inMST[to]) continue;

            inMST[to] = true;
            System.out.println("Edge added to MST: " + minEdge); // or perform any other operation with the edge.

            for (Edge edge : graph.get(to)) {
                if (!inMST[edge.to]) {
                    pq.offer(edge);
                }
            }
        }
    }

    static class Edge {
        int to;
        int weight;

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

        @Override
        public String toString() {
            return "(" + to + ", " + weight + ")";
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

在这个例子中，List<List<Edge>> 是一个邻接表，用于存储图中的边及其权重。computeMST 方法实现了 Prim 算法的核心逻辑。

请注意，这只是一个简化的示例，实际应用中可能需要更复杂的数据结构和错误处理。

为了更全面地理解Prim算法在Java中的实现，我们可以进一步扩展之前的代码示例，包括构建图的方法和一个主函数来运行算法。下面是一个完整的示例，我们将构建一个包含5个顶点的图，并使用Prim算法找到最小生成树。

首先，我们需要定义顶点和边的数据结构，以及如何构建图的邻接表。然后，我们将实现Prim算法，并在主函数中调用它。

import java.util.*;

public class PrimMST {
    static class Edge implements Comparable<Edge> {
        int to;
        int weight;

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

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    private final List<List<Edge>> graph;
    private boolean[] inMST;

    public PrimMST(int numVertices) {
        this.graph = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }
        this.inMST = new boolean[numVertices];
    }

    public void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
        graph.get(to).add(new Edge(from, weight)); // Since the graph is undirected.
    }

    public void computeMST() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        inMST[0] = true; // Start from vertex 0.
        for (Edge edge : graph.get(0)) {
            pq.offer(edge);
        }

        while (!pq.isEmpty()) {
            Edge minEdge = pq.poll();
            int to = minEdge.to;
            if (inMST[to]) continue;

            inMST[to] = true;
            System.out.println("Edge added to MST: " + minEdge);

            for (Edge edge : graph.get(to)) {
                if (!inMST[edge.to]) {
                    pq.offer(edge);
                }
            }
        }
    }

    public static void main(String[] args) {
        PrimMST prim = new PrimMST(5); // Create a graph with 5 vertices.
        
        // Add edges to the graph.
        prim.addEdge(0, 1, 2);
        prim.addEdge(0, 3, 6);
        prim.addEdge(1, 2, 3);
        prim.addEdge(1, 3, 8);
        prim.addEdge(1, 4, 5);
        prim.addEdge(2, 4, 7);
        prim.addEdge(3, 4, 9);

        // Compute the minimum spanning tree.
        prim.computeMST();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

在这个例子中：

1. 我们创建了一个Edge类来存储边的信息，并实现了Comparable接口以便于在优先级队列中进行比较。
2. PrimMST构造函数初始化了图的邻接表和inMST数组。
3. addEdge方法用于添加无向边到图中。
4. computeMST方法执行Prim算法，输出被添加到最小生成树中的边。

在主函数中，我们创建了一个PrimMST对象并添加了一些边，最后调用了computeMST方法来计算最小生成树。这个例子中的图和边的权重是随机选择的，你可以根据自己的需求调整它们。

Kruskal算法是一种寻找加权图的最小生成树(Minimum Spanning Tree, MST)的算法。以下是Kruskal算法的一个Java实现：

import java.util.*;

public class KruskalMST {

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

        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;
        }
    }

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

    static void union(int subset[], int x, int y) {
        int xroot = find(subset, x);
        int yroot = find(subset, y);

        if (xroot != yroot) {
            subset[xroot] = yroot;
        }
    }

    static void kruskalMST(Edge edge[], int V) {
        Arrays.sort(edge, 0, edge.length);

        int index = 0;
        int e = 0;
        int[] subset = new int[V];

        Arrays.fill(subset, -1);

        while (e < V - 1) {
            Edge next_edge = edge[index++];

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

            if (x != y) {
                e++;
                System.out.println("Edge included in MST: (" + next_edge.src + ", " + next_edge.dest + ") with weight " + next_edge.weight);
                union(subset, x, y);
            }
        }
    }

    public static void main(String[] args) {
        int V = 4; // Number of vertices in graph
        Edge edge[] = new Edge[5]; // An array of an unsorted list of edges

        // Allocate memory for creating edges
        edge[0] = new Edge(0, 1, 10);
        edge[1] = new Edge(0, 2, 6);
        edge[2] = new Edge(0, 3, 5);
        edge[3] = new Edge(1, 3, 15);
        edge[4] = new Edge(2, 3, 4);

        kruskalMST(edge, V);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

在这个实现中：

• Edge类用于表示图中的边，包含了源顶点、目标顶点和边的权重。
• find函数用于查找顶点所属的子集。
• union函数用于合并两个子集。
• kruskalMST函数执行Kruskal算法，先对所有边按权重排序，然后依次选取权重最小且不会形成环的边加入到MST中。
• 主函数创建了一个图的边列表，并调用kruskalMST函数来计算最小生成树。

请注意，上述代码仅适用于没有自环和多重边的简单图。如果图中包含自环或多重边，你可能需要在代码中增加额外的逻辑来处理这些情况。

如果你想要扩展上面的KruskalMST类，以便更好地理解整个过程或者增加一些额外的功能，例如跟踪MST的总权重或输出完整的MST边集合，可以考虑以下的代码扩展：

import java.util.*;

public class KruskalMST {

    static class Edge implements Comparable<Edge> {
        int src, dest, weight;
        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;
        }
    }

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

    static void union(int subset[], int x, int y) {
        int xroot = find(subset, x);
        int yroot = find(subset, y);

        if (xroot != yroot) {
            subset[xroot] = yroot;
        }
    }

    static void kruskalMST(Edge edge[], int V) {
        Arrays.sort(edge, 0, edge.length);

        List<Edge> mstEdges = new ArrayList<>();
        int index = 0;
        int e = 0;
        int[] subset = new int[V];
        Arrays.fill(subset, -1);

        while (e < V - 1) {
            Edge next_edge = edge[index++];

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

            if (x != y) {
                e++;
                mstEdges.add(next_edge);
                union(subset, x, y);
            }
        }

        int totalWeight = 0;
        for (Edge edge : mstEdges) {
            totalWeight += edge.weight;
            System.out.println("Edge included in MST: (" + edge.src + ", " + edge.dest + ") with weight " + edge.weight);
        }

        System.out.println("Total weight of the MST: " + totalWeight);
    }

    public static void main(String[] args) {
        int V = 4; // Number of vertices in graph
        Edge edge[] = new Edge[5]; // An array of an unsorted list of edges

        edge[0] = new Edge(0, 1, 10);
        edge[1] = new Edge(0, 2, 6);
        edge[2] = new Edge(0, 3, 5);
        edge[3] = new Edge(1, 3, 15);
        edge[4] = new Edge(2, 3, 4);

        kruskalMST(edge, V);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

在这个扩展版本中，我做了以下修改：

• 添加了一个List<Edge>类型的变量mstEdges来存储MST中的所有边。
• 在kruskalMST方法的最后，遍历了mstEdges列表并计算了MST的总权重，同时输出每条边的信息。
• 最后输出了MST的总权重。

这样，你不仅可以看到哪些边被包括在MST中，还可以知道MST的总权重是多少。这有助于更全面地理解Kruskal算法的结果。

城市间的高速公路网络优化

假设你是一家交通规划公司的数据分析师，你的任务是帮助规划一个国家的新高速公路网络。该国目前有多个城市，政府希望在这些城市之间建立一个高速公路网络，以促进经济发展和人员流动，但预算有限。因此，目标是在确保所有城市都能通过高速公路网络相连的前提下，使总建设成本最小。

数据：

• 城市数量：N（例如，N=10）
• 每对城市之间的距离（成本）：C_ij，表示城市i到城市j的建设成本。

问题：

如何选择一组高速公路连接，使得所有城市都能通过高速公路网络到达，同时总成本最小？

解决方案：Kruskal算法

Kruskal算法可以用来解决这个问题。它会找出一个最小生成树（MST），即所有城市都能通过唯一的路径相连，而总成本最低。

步骤：

1. 收集数据：获取所有城市之间的距离或建设成本。
2. 创建边列表：将所有可能的城市间连接作为边，记录每条边的权重（成本）。
3. 排序：对边列表按成本进行升序排序。
4. 初始化：为每个城市创建一个单独的集合（森林中的单独树）。
5. Kruskal算法执行：
   • 从成本最低的边开始，检查每条边的两个端点是否属于同一集合。
   • 如果不属于同一集合，则将这条边加入MST中，并将这两个端点所在的集合合并。
   • 继续处理下一条边，直到所有城市都被包含在同一个集合中。
6. 结果：最终得到的边集就是最小生成树，即最优的高速公路网络布局。

Java代码示例：

import java.util.*;

public class HighwayNetworkOptimizer {

    static class Edge implements Comparable<Edge> {
        int cityA, cityB, cost;

        public Edge(int cityA, int cityB, int cost) {
            this.cityA = cityA;
            this.cityB = cityB;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

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

    static void union(int[] parent, int x, int y) {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
        if (xroot != yroot)
            parent[xroot] = yroot;
    }

    static void optimizeHighwayNetwork(Edge[] edges, int N) {
        Arrays.sort(edges);
        int[] parent = new int[N];
        Arrays.fill(parent, -1);
        List<Edge> mst = new ArrayList<>();

        for (Edge edge : edges) {
            int xroot = find(parent, edge.cityA);
            int yroot = find(parent, edge.cityB);
            if (xroot != yroot) {
                mst.add(edge);
                union(parent, xroot, yroot);
            }
        }

        System.out.println("Optimized Highway Network:");
        int totalCost = 0;
        for (Edge edge : mst) {
            System.out.println("Connect cities " + edge.cityA + " and " + edge.cityB + " with cost " + edge.cost);
            totalCost += edge.cost;
        }
        System.out.println("Total cost: " + totalCost);
    }

    public static void main(String[] args) {
        int N = 10; // Number of cities
        Edge[] edges = new Edge[45]; // Assume full connectivity between cities

        // Populate the edges array with costs (distances) between cities.
        // For simplicity, let's assume some random values here.
        edges[0] = new Edge(0, 1, 10);
        edges[1] = new Edge(0, 2, 15);
        // ... populate remaining edges similarly.

        optimizeHighwayNetwork(edges, N);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

在这个案例中，我们使用Kruskal算法找到了成本最低的高速公路网络布局，满足了政府的需求，同时也展示了算法的实际应用价值。