A greedy algorithm is a method for solving optimization problems by making the locally optimal choice at each stage with the hope of finding a global optimum. The key characteristic of a greedy algorithm is that it makes the locally optimal choice at each step without considering the consequences of that choice on future steps. This approach can lead to efficient solutions, but it is not always the best method for solving a problem. In this blog post, we will explore how to implement a greedy algorithm in Java.

One of the most common applications of greedy algorithms is in the field of graph theory. A classic example is the Kruskal’s algorithm for finding the minimum spanning tree of a connected, undirected graph. The algorithm starts with an empty set of edges and iteratively adds the edge with the lowest weight that does not form a cycle. Here is an example of Kruskal’s algorithm implemented in Java:

public class Kruskal {
    static int V = 9;
    static int E = 14;

    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 xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }

    static void kruskalMST(int[][] graph) {
        int parent[] = new int[V];
        Arrays.fill(parent, -1);

        int edgeCount = 0;
        int totalWeight = 0;
        while (edgeCount < V - 1) {
            int min = Integer.MAX_VALUE;
            int x = 0, y = 0;
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (graph[i][j] != 0 && graph[i][j] < min) {
                        min = graph[i][j];
                        x = i;
                        y = j;
                    }
                }
            }

            int x_root = find(parent, x);
            int y_root = find(parent, y);

            if (x_root != y_root) {
                totalWeight += min;
                edgeCount++;
                union(parent, x_root, y_root);
            }
            graph[x][y] = graph[y][x] = 0;
        }
        System.out.println("Weight of MST is " + totalWeight);
    }
}

Another example of a greedy algorithm is the Dijkstra’s algorithm for finding the shortest path in a weighted graph. The algorithm starts with a single source vertex and iteratively relaxes the edges to find the shortest path to all other vertices. Here is an example of Dijkstra’s algorithm implemented in Java:

public class Dijkstra {
    static int V = 9;

    static int minDistance(int dist[], boolean sptSet[]) {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
                  }
                   return min_index;
                  }
static void dijkstra(int graph[][], int src) {
    int dist[] = new int[V];
    boolean sptSet[] = new boolean[V];

    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

static void printSolution(int dist[]) {
    System.out.println("Vertex Distance from Source");
    for (int i = 0; i < V; i++)
        System.out.println(i + " \t\t " + dist[i]);
}
}