check

package src;
import java.util.*;


public class prims {

    public static void main(String[] args) {
        int w[][] = new int[10][10];
        int n, i, j, s, k = 0, min, sum = 0, u = 0, v = 0, flag = 0;
        int sol[] = new int[10];

        System.out.println("Enter no. of vertices");
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (i = 1; i <= n; i++) {
            sol[i] = 0;
        }

        System.out.println("Enter the weighted graph");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                w[i][j] = sc.nextInt();
            }
        }

        System.out.println("Enter the Source vertex");
        s = sc.nextInt();

        sol[s] = 1;
        k = 1;

        while (k <= n - 1) {
            min = 99;
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++) {
                    if (sol[i] == 1 && sol[j] == 0) {
                        if (i != j && min > w[i][j]) {
                            min = w[i][j];
                            u = i;
                            v = j;
                        }
                    }
                }
            }
            sol[v] = 1;
            sum = sum + min;
            k++;
            System.out.println(u + "->" + v + "=" + min);
        }

        for (i = 1; i <= n; i++) {
            if (sol[i] == 0) {
                flag = 1;
            }
        }

        if (flag == 1) {
            System.out.println("No spanning Tree");
        } else {
            System.out.println("The cost of minimum spanning tree is " + sum);
        }
        sc.close();
    }
}

package src;
import java.util.*;
public class kruskal {
	static int[] parent=new int[50];
	static int[][] cost=new int[10][10];
	static int a, b, i, j, u, v, n, min=1, noe=1, mincost=0;
	static int find(int w) {
		while(parent[w]!=0) {
			w=parent[w];
			
		}
		return w;
	}
	static void union() {
		if(u!=v) {
			noe++;
			System.out.println(noe-1+"Edge("+a+","+b+")="+min);
			mincost+=min;
			parent[v]=u;
		}
		cost[a][b]=cost[b][a]=999;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the unumber of vertices:");
		n=sc.nextInt();
		System.out.println("Enter the cost adjacency matrix, 999 for no direct path:");
		for(i=1;i<=n;i++) {
			for(j=1;j<=n;j++) {
				cost[i][j]=sc.nextInt();
			}
		}
		while(noe<n) {
			min=999;
			for(i=1;i<=n;i++) {
				for(j=1;j<=n;j++) {
					if(cost[i][j]<min) {
						min=cost[i][j];
						a=u=i;
						b=v=j;
						
					}
				}
			}
			u=find(u);
			v=find(v);
			union();
		}
		System.out.println("Minimum cost ="+mincost);
	}

}

package src;
import java.util.*;
public class dijkstra {




    public int distance[] = new int[10];
    public int cost[][] = new int[10][10];

    public void calc(int n, int s) {
        int flag[] = new int[n + 1];
        int i, minpos = 1, k, c, minimum;

        for (i = 1; i <= n; i++) {
            flag[i] = 0;
            this.distance[i] = this.cost[s][i];
        }

        c = 2;
        while (c <= n) {
            minimum = 999;
            for (k = 1; k <= n; k++) {
                // Fixed: replaced 'i' with 'k' in minimum = this.distance[k]
                if (this.distance[k] < minimum && flag[k] != 1) {
                    minimum = this.distance[k];
                    minpos = k;
                }
            }
            
            flag[minpos] = 1;
            c++;

            for (k = 1; k <= n; k++) {
                if (this.distance[minpos] + this.cost[minpos][k] < this.distance[k] && flag[k] != 1) {
                    this.distance[k] = this.distance[minpos] + this.cost[minpos][k];
                }
            }
        }
    }

    public static void main(String[] args) {
        int nodes, source, i, j;
        Scanner in = new Scanner(System.in);

        System.out.println("Enter the number of nodes");
        nodes = in.nextInt();

        dijkstra d = new dijkstra();

        System.out.println("Enter the cost Matrix Weights");
        for (i = 1; i <= nodes; i++) {
            for (j = 1; j <= nodes; j++) {
                d.cost[i][j] = in.nextInt();
                if (d.cost[i][j] == 0) {
                    d.cost[i][j] = 999;
                }
            }
        }

        System.out.println("Enter the source vertex");
        source = in.nextInt();

        d.calc(nodes, source);

        System.out.println("The shortest path from source " + source + " to all other vertices are:");
        for (i = 1; i <= nodes; i++) {
            if (i != source) {
                System.out.println("Source: " + source + " destination : " + i + " Mincost : " + d.distance[i]);
            }
        }
    }
}

package src;
import java.util.Scanner;
public class zoknapsack {


    int n, c, p[], w[], v[][];

    public zoknapsack (int n, int c, int[] p, int[] w) {
        this.n = n;
        this.c = c;
        this.p = p;
        this.w = w;
        this.v = new int[n + 1][c + 1];
    }

    void compute() {
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= c; ++j) {
                if (i == 0 || j == 0) {
                    v[i][j] = 0;
                } else {
                    if (j - w[i] >= 0) {
                        v[i][j] = max(v[i - 1][j], p[i] + v[i - 1][j - w[i]]);
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        System.out.println("Optimal Solution: " + v[n][c]);
        traceback();
    }

    void traceback() {
        System.out.println("The objects picked up into knapsack are: ");
        int i = n;
        int j = c;
        while (i > 0) {
            if (v[i][j] != v[i - 1][j]) {
                System.out.print(i + " ");
                j = j - w[i];
            }
            i--;
        }
    }

    private int max(int i, int j) {
        return (i > j) ? i : j;
    }

    public static void main(String[] args) {
        int n;
        int c;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of objects");
        n = sc.nextInt();
        int[] p = new int[n + 1];
        int[] w = new int[n + 1];
        System.out.println("Enter capacity of knapsack");
        c = sc.nextInt();
        System.out.println("Enter the profit for each of the " + n + " objects");
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }
        System.out.println("Enter weight for each of the " + n + " objects");
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        zoknapsack  dk = new zoknapsack (n, c, p, w);
        dk.compute();
        sc.close();
    }
}

package src;
import java.util.*;
public class floyd {


    void flyd(int[][] w, int n) {
        int i, j, k;
        for (k = 1; k <= n; k++) {
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++) {
                    w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
                }
            }
        }
    }

    public static void main(String[] args) {
        int a[][] = new int[10][10];
        int n, i, j;
        System.out.println("Enter no of vertices");
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        System.out.println("Enter the weighted matrix");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        floyd f = new floyd();
        f.flyd(a, n);
        System.out.println("The shortest path matrix is");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}

package src;

import java.util.*;

public class subset {

    static int c = 0;

    public static void main(String[] args) {
        int w[] = new int[10];
        int n, d, i, sum = 0;
        int x[] = new int[10];
        Scanner sc = new Scanner(System.in);

        System.out.println("****SUBSET PROBLEM****");
        System.out.println("Enter the no of elements");
        n = sc.nextInt();

        System.out.println("Enter the elements in increasing order");
        for (i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }

        System.out.println("Enter the value of d:");
        d = sc.nextInt();

        for (i = 0; i < n; i++) {
            sum = sum + w[i];
        }
        System.out.println("SUM:" + sum);

        if (sum < d || w[0] > d) {
            System.out.println("Subset is not possible");
            System.out.println("*****************");
            System.exit(0);
        }

        finalsubset(0, 0, sum, x, w, d);

        if (c == 0) {
            System.out.println("subset is not possible");
        }
        
        System.out.println("\n *********");
        sc.close();
    }

    static void finalsubset(int cs, int k, int r, int x[], int w[], int d) {
        x[k] = 1;
        if (cs + w[k] == d) {
            c++;
            System.out.println("\nSolution " + c + " is {");
            for (int i = 0; i <= k; i++) {
                if (x[i] == 1) {
                    System.out.print(w[i] + " ");
                }
            }
            System.out.print("}");
        } 
        else if ((cs + w[k] + w[k + 1]) <= d) {
            finalsubset(cs + w[k], k + 1, r - w[k], x, w, d);
        }

        if ((cs + r - w[k]) >= d && (cs + w[k + 1]) <= d) {
            x[k] = 0;
            finalsubset(cs, k + 1, r - w[k], x, w, d);
        }
    }
}

package src;

import java.util.*;

public class nqueen {

    public static boolean isSafe(int row, int col, char[][] board) {
        // Check horizontal row
        for (int j = 0; j < board.length; j++) {
            if (board[row][j] == 'Q') {
                return false;
            }
        }

        // Check vertical column
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        int r = row;
        // Check top-left diagonal
        for (int c = col; c >= 0 && r >= 0; c--, r--) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check top-right diagonal
        for (int c = col; c < board.length && r >= 0; r--, c++) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check bottom-left diagonal
        for (int c = col; c >= 0 && r < board.length; r++, c--) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check bottom-right diagonal
        for (int c = col; c < board.length && r < board.length; c++, r++) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static void saveBoard(char[][] board, List<List<String>> allBoards) {
        List<String> newBoard = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String row = "";
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'Q') {
                    row += 'Q';
                } else {
                    row += '.';
                }
            }
            newBoard.add(row);
        }
        allBoards.add(newBoard);
    }

    public static void solve(char[][] board, List<List<String>> allBoards, int col) {
        if (col == board.length) {
            saveBoard(board, allBoards);
            return;
        }

        for (int row = 0; row < board.length; row++) {
            if (isSafe(row, col, board)) {
                board[row][col] = 'Q';
                solve(board, allBoards, col + 1);
                board[row][col] = '.'; // Backtrack
            }
        }
    }

    public static void solution(int n) {
        List<List<String>> allBoards = new ArrayList<>();
        char[][] board = new char[n][n];

        // Initialize the board with '.' otherwise it contains default null characters
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        solve(board, allBoards, 0);

        // Print all valid configurations
        for (List<String> aboard : allBoards) {
            for (int i = 0; i < aboard.size(); i++) {
                System.out.println(aboard.get(i));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        solution(4);
    }														
}

package src;
import java.util.*;

public class tsp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c[][] = new int[10][10];
        int tour[] = new int[10]; 
        int i, j, cost;
        
        System.out.println("Enter no of cities"); 
        int n = sc.nextInt();
        
        if (n == 1) {
            System.out.println("Path is not possible");
            System.exit(0);
        }
        
        System.out.println("Enter the cost matrix"); 
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                c[i][j] = sc.nextInt();
            }
        }
        
        for (i = 1; i <= n; i++) {
            tour[i] = i; 
        }
        
        cost = tspdp(c, tour, 1, n);
        
        System.out.println("The optimal tour is = ");
        for (i = 1; i <= n; i++) {
            System.out.print(tour[i] + "->");
        }
        System.out.println("1");
        System.out.println("\tMin Cost = " + cost);
        
        sc.close();
    }
    
    static int tspdp(int c[][], int tour[], int start, int n) {
        int mintour[] = new int[10];
        int temp[] = new int[10]; // Fixed missing space here
        int mincost = 999, ccost, i, j, k; 
        
        if (start == n - 1) {
            return (c[tour[n - 1]][tour[n]] + c[tour[n]][1]); 
        }
        
        for (i = start + 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                temp[j] = tour[j]; 
            }
            
            // Swap cities to check a new permutation route
            temp[start + 1] = tour[i];
            temp[i] = tour[start + 1];
            
            ccost = tspdp(c, temp, start + 1, n);
            if ((c[tour[start]][tour[i]] + ccost) < mincost) { 
                mincost = c[tour[start]][tour[i]] + ccost;
                for (k = 1; k <= n; k++) {
                    mintour[k] = temp[k];
                }
            }
        }
        
        for (i = 1; i <= n; i++) {
            tour[i] = mintour[i]; 
        }
        
        return mincost;
    }
}

package src;
import java.util.Scanner;
public class warshall{


    void flyd(int[][] w, int n) {
        int i, j, k;
        for (k = 1; k <= n; k++) {
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++) {
                    w[i][j] = (w[i][j] != 0) || ((w[i][k] != 0) && (w[k][j] != 0)) ? 1 : 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        int a[][] = new int[10][10];
        int n, i, j;
        System.out.println("Enter no of vertices");
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        System.out.println("Enter the weighted matrix");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        warshall f = new warshall();
        f.flyd(a, n);
        System.out.println("The shortest path matrix is");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }
}