Write a program to implement the Knapsack problem using the greedy method 

import java.util.Arrays;
import java.util.Scanner;

class Item implements Comparable<Item> {
    int value, weight;
    double ratio; // value/weight ratio

    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
        this.ratio = (double) value / weight;
    }

    // Sort items by decreasing ratio
    @Override
    public int compareTo(Item other) {
        if (this.ratio < other.ratio) return 1;
        else if (this.ratio > other.ratio) return -1;
        else return 0;
    }
}

public class FractionalKnapsack {

    public static double fractionalKnapsack(int W, Item[] items) {
        Arrays.sort(items);

        double totalValue = 0.0;
        int currentWeight = 0;

        for (Item item : items) {
            if (currentWeight + item.weight <= W) {
                // Take whole item
                currentWeight += item.weight;
                totalValue += item.value;
            } else {
                // Take fraction of item
                int remain = W - currentWeight;
                totalValue += item.ratio * remain;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of items: ");
        int n = sc.nextInt();

        Item[] items = new Item[n];

        System.out.println("Enter value and weight of each item:");
        for (int i = 0; i < n; i++) {
            int value = sc.nextInt();
            int weight = sc.nextInt();
            items[i] = new Item(value, weight);
        }

        System.out.print("Enter capacity of knapsack: ");
        int capacity = sc.nextInt();

        double maxValue = fractionalKnapsack(capacity, items);
        System.out.println("Maximum value in knapsack = " + maxValue);

        sc.close();
    }
}



-------------------------------------------------------------------------------------------
Prims greedy

import java.util.Scanner;

public class PrimsAlgorithm {
    private static final int INF = 9999999;

    public static void primMST(int[][] graph, int V) {
        int[] parent = new int[V];    // Array to store constructed MST
        int[] key = new int[V];       // Key values to pick minimum weight edge
        boolean[] mstSet = new boolean[V]; // To represent set of vertices included in MST

        // Initialize all keys as infinite
        for (int i = 0; i < V; i++) {
            key[i] = INF;
            mstSet[i] = false;
        }

        // Always include first vertex in MST
        key[0] = 0;     // Make key 0 so that this vertex is picked first
        parent[0] = -1; // First node is always root of MST

        for (int count = 0; count < V - 1; count++) {
            // Pick the minimum key vertex from the set of vertices not yet included in MST
            int u = minKey(key, mstSet, V);
            mstSet[u] = true;

            // Update key and parent index of the adjacent vertices
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph, V);
    }

    // Utility function to find vertex with minimum key value
    private static int minKey(int[] key, boolean[] mstSet, int V) {
        int min = INF, minIndex = -1;
        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    // Print MST stored in parent[]
    private static void printMST(int[] parent, int[][] graph, int V) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of vertices: ");
        int V = sc.nextInt();

        int[][] graph = new int[V][V];
        System.out.println("Enter adjacency matrix (0 if no edge):");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        primMST(graph, V);
        sc.close();
    }
}



1. Prim’s Algorithm — Sample Input
Suppose you have 5 vertices (0 to 4) and the adjacency matrix for the weighted graph:

yaml
Copy
Edit
Enter number of vertices: 5
Enter adjacency matrix (0 if no edge):
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0


--------------------------------------------------------------------------------------------------
Kruskal greedy


package Graph;

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

    // sorting edge by weight in ascending order
    public int compareTo(Edge compareEdge) {
        return this.weight - compareEdge.weight;
    }
}

class Subset {
    int parent, rank;
}

public class Kruskal {
    int V, E;
    Edge[] edges;

    public Kruskal(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
    }

    // finding func with path compression
    int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i) {
            subsets[i].parent = find(subsets, subsets[i].parent);
        }
        return subsets[i].parent;
    }

    // union function with rank opt
    void union(Subset[] subsets, int x, int y) {
        int rootX = find(subsets, x);
        int rootY = find(subsets, y);

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

    void kruskalMST() {
        Edge[] result = new Edge[V - 1];
        int e = 0;
        int i = 0;

        // 1: sort the edges
        Arrays.sort(edges);

        // Allocate the memory for subsets
        Subset[] subsets = new Subset[V];
        for (int v = 0; v < V; v++) {
            subsets[v] = new Subset();
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
        // 2:pick the smallest edge and check for cycle
        while (e < V - 1) {
            Edge nextEdge = edges[i++];

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

            // If adding this edge doesn't cause a cycle, include it in MST
            if (x != y) {
                result[e++] = nextEdge;
                union(subsets, x, y);
            }

        }
        // Print the MST
        System.out.println("Edges in Minimum Spanning Tree:");
        for (i = 0; i < e; i++) {
            System.out.println(result[i].src + " - " + result[i].dest + " : " + result[i].weight);
        }

    }

    public static void main(String[] args) {
        int V = 4; // Number of vertices
        int E = 5; // Number of edges
        Kruskal graph = new Kruskal(V, E);

        // Adding edges (source, destination, weight)
        graph.edges[0] = new Edge(0, 1, 10);
        graph.edges[1] = new Edge(0, 2, 6);
        graph.edges[2] = new Edge(0, 3, 5);
        graph.edges[3] = new Edge(1, 3, 15);
        graph.edges[4] = new Edge(2, 3, 4);

        // Run Kruskal's Algorithm
        graph.kruskalMST();
    }
}




Kruskal’s Algorithm — Sample Input
For the same graph above, you can enter edges explicitly:

mathematica
Copy
Edit
Enter number of vertices: 5
Enter number of edges: 7
Enter edges (source destination weight):
0 1 2
0 3 6
1 2 3
1 3 8
1 4 5
2 4 7
3 4 9



----------------------------------------------------------------------------------------------------------------------------------
Write a program to implement a Single source shortest path (Dijkstra’s algorithm) using the greedy method 

import java.util.Scanner;

public class DijkstraAlgorithm {

    private static final int INF = 9999999;

    // Function to find vertex with minimum distance value from set of vertices not yet processed
    private static int minDistance(int[] dist, boolean[] sptSet, int V) {
        int min = INF, minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    public static void dijkstra(int[][] graph, int src, int V) {
        int[] dist = new int[V];        // Output array. dist[i] will hold shortest distance from src to i
        boolean[] sptSet = new boolean[V]; // sptSet[i] will be true if vertex i included in shortest path tree

        // Initialize all distances as infinite and sptSet[] as false
        for (int i = 0; i < V; i++) {
            dist[i] = INF;
            sptSet[i] = false;
        }

        // Distance of source vertex from itself is always 0
        dist[src] = 0;

        // Find shortest path for all vertices
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet, V);
            sptSet[u] = true;

            // Update dist value of adjacent vertices of the picked vertex.
            for (int v = 0; v < V; v++) {
                // Update dist[v] only if:
                // 1. There is an edge from u to v
                // 2. Vertex v is not in sptSet
                // 3. Total weight of path from src to v through u is smaller than current dist[v]
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != INF
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist, V, src);
    }

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of vertices: ");
        int V = sc.nextInt();

        int[][] graph = new int[V][V];

        System.out.println("Enter adjacency matrix (0 if no edge):");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        System.out.print("Enter source vertex: ");
        int src = sc.nextInt();

        dijkstra(graph, src, V);
        sc.close();
    }
}




Sample Input:
yaml
Copy
Edit
Enter number of vertices: 5
Enter adjacency matrix (0 if no edge):
0 10 0 0 5
0 0 1 0 2
0 0 0 4 0
7 0 6 0 0
0 3 9 2 0
Enter source vertex: 0

