How to implement Kruskal algorithm using java-javaTutorial-php.cn

How to implement Kruskal algorithm using java

WBOY

Release： 2023-09-19 11:39:22

Original

1361 people have browsed it

How to implement Kruskal algorithm using java

How to use Java to implement the Kruskal algorithm

The Kruskal algorithm is an algorithm commonly used to solve the minimum spanning tree problem. It uses edges as the entry point to gradually build the minimum spanning tree. Tree. In this article, we will detail how to implement Kruskal's algorithm using Java and provide specific code examples.

Algorithm Principle
The basic principle of Kruskal algorithm is to sort all edges according to the weight from small to large, and then select the edges in order from small to large, but cannot form a cycle. . The specific implementation steps are as follows:
- Sort all edges according to their weight from small to large.
- Create an empty set to store the edges of the minimum spanning tree.
- Traverse the sorted edges and determine whether the two vertices of the current edge are in the same set. If not in the same set, add the current edge to the set of minimum spanning trees and merge the two vertices into one set.
- Continue traversing until the number of edges of the minimum spanning tree is equal to the number of vertices minus one.
Java code implementation
The following is a code example using Java language to implement the Kruskal algorithm:

import java.util.*;

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

    public int compareTo(Edge edge) {
        return this.weight - edge.weight;
    }
}

class Subset {
    int parent, rank;
}

class Graph {
    int V, E;
    Edge[] edges;

    public Graph(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
        for (int i = 0; i < e; ++i)
            edges[i] = new Edge();
    }

    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;
    }

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

        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    void KruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; ++i)
            result[i] = new Edge();

        Arrays.sort(edges);

        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; ++i)
            subsets[i] = new Subset();

        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0;

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

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

            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }

        System.out.println("Following are the edges in the constructed MST:");
        int minimumCost = 0;
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
            minimumCost += result[i].weight;
        }
        System.out.println("Minimum Cost Spanning Tree: " + minimumCost);
    }
}

public class KruskalAlgorithm {
    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        Graph graph = new Graph(V, E);

        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;

        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;

        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;

        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;

        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;

        graph.KruskalMST();
    }
}

Copy after login

The above code implements a simple graph class ( Graph), including edge class (Edge) and union search class (Subset). In the main function, we create a graph object, add edges and call the KruskalMST() method to get the minimum spanning tree.

Result Analysis
After testing, the above code can correctly output the following results:

Following are the edges in the constructed MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

Copy after login

This means that the minimum spanning tree constructed contains 3 edges, and the weight of The sum is 19.

Summary:
Through this article, we introduced in detail how to use Java to implement the Kruskal algorithm, and attached specific code examples. I hope this article can help everyone better understand and apply the Kruskal algorithm.

The above is the detailed content of How to implement Kruskal algorithm using java. For more information, please follow other related articles on the PHP Chinese website!