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

Scanner sc=new Scanner(System.in);

System.out.println(“Enter the number of vertices:”);
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();
}
}

2222222222222

import java.util.*;

public class Kruskal {

static int parent[] = new int[10];

static int find(int i){
while(parent[i]!=0)
i=parent[i];
return i;
}

static void union(int i,int j){
parent[j]=i;
}

public static void main(String args[]){

int a[][]=new int[10][10];
int n,i,j,min,u=0,v=0,sum=0,edge=1;

Scanner sc=new Scanner(System.in);

System.out.println(“Enter number of vertices”);
n=sc.nextInt();

System.out.println(“Enter cost matrix”);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=sc.nextInt();

while(edge<n){

min=999;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]<min){
min=a[i][j];
u=i;
v=j;
}

int p=find(u);
int q=find(v);

if(p!=q){
union(p,q);
System.out.println(u+”->”+v+”=”+min);
sum+=min;
edge++;
}

a[u][v]=a[v][u]=999;
}

System.out.println(“Minimum Cost = “+sum);
}
}

333333333333333333

import java.util.*;

public class Dijkstra {

public static void main(String args[]) {

int n,s,i,j,u=0;
int cost[][]=new int[10][10];
int dist[]=new int[10];
int visited[]=new int[10];

Scanner sc=new Scanner(System.in);

System.out.println(“Enter number of vertices”);
n=sc.nextInt();

System.out.println(“Enter cost matrix”);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=sc.nextInt();

System.out.println(“Enter source vertex”);
s=sc.nextInt();

for(i=1;i<=n;i++){
dist[i]=cost[s][i];
visited[i]=0;
}

visited[s]=1;

for(int count=2;count<=n;count++){

int min=999;

for(i=1;i<=n;i++)
if(visited[i]==0 && dist[i]<min){
min=dist[i];
u=i;
}

visited[u]=1;

for(i=1;i<=n;i++)
if(visited[i]==0 && dist[i] > dist[u]+cost[u][i])
dist[i]=dist[u]+cost[u][i];
}

System.out.println(“Shortest Path:”);

for(i=1;i<=n;i++)
if(i!=s)
System.out.println(s+” -> “+i+” = “+dist[i]);

sc.close();
}
}

444444444444

import java.util.*;

public class Floyd {

public static void main(String args[]) {

int a[][]=new int[10][10];
int n,i,j,k;

Scanner sc=new Scanner(System.in);

System.out.println(“Enter number of vertices”);
n=sc.nextInt();

System.out.println(“Enter cost matrix”);

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=sc.nextInt();

for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=Math.min(a[i][j],a[i][k]+a[k][j]);

System.out.println(“All Pair Shortest Path Matrix”);

for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
System.out.print(a[i][j]+” “);
System.out.println();
}
}
}

5555555555555555

import java.util.*;

public class Warshall {

void warshall(int a[][],int n){

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=(a[i][j]!=0 ||
(a[i][k]!=0 && a[k][j]!=0))?1:0;
}

public static void main(String args[]){

int a[][]=new int[10][10];

Scanner sc=new Scanner(System.in);

System.out.println(“Enter no of vertices”);
int n=sc.nextInt();

System.out.println(“Enter the weighted matrix”);

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=sc.nextInt();

Warshall w=new Warshall();
w.warshall(a,n);

System.out.println(“The shortest path matrix is”);

for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
System.out.print(a[i][j]+” “);
System.out.println();
}
}
}

666666666666

import java.util.*;

public class DKnapsack {

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

DKnapsack(int n,int c,int p[],int w[]){
this.n=n;
this.c=c;
this.p=p;
this.w=w;
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])
v[i][j]=Math.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]);
}

public static void main(String args[]){

Scanner sc=new Scanner(System.in);

System.out.println(“Enter number of objects”);
int n=sc.nextInt();

System.out.println(“Enter capacity”);
int c=sc.nextInt();

int p[]=new int[n+1];
int w[]=new int[n+1];

System.out.println(“Enter profits”);
for(int i=1;i<=n;i++)
p[i]=sc.nextInt();

System.out.println(“Enter weights”);
for(int i=1;i<=n;i++)
w[i]=sc.nextInt();

DKnapsack dk=new DKnapsack(n,c,p,w);
dk.compute();
}
}

77777777777777

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

int mincost = 999;
int ccost, i, j;

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

temp[start + 1] = tour[i];
temp[i] = tour[start + 1];

if ((c[tour[start]][tour[i]] +
(ccost = tspdp(c, temp, start + 1, n))) < mincost) {

mincost = c[tour[start]][tour[i]] + ccost;

for (j = 1; j <= n; j++)
mintour[j] = temp[j];
}
}

for (i = 1; i <= n; i++)
tour[i] = mintour[i];

return mincost;
}
}

88888888888888

package sample_programs;

import java.util.*;

public class Queen {

public static boolean isSafe(int row, int col, char[][] board) {

for (int j = 0; j < board.length; j++) {
if (board[row][j] == ‘Q’) {
return false;
}
}

for (int i = 0; i < board.length; i++) {
if (board[i][col] == ‘Q’) {
return false;
}
}

int r = row;

for (int c = col; c >= 0 && r >= 0; c–, r–) {
if (board[r][c] == ‘Q’) {
return false;
}
}

r = row;

for (int c = col; c >= 0 && r < board.length; c–, r++) {
if (board[r][c] == ‘Q’) {
return false;
}
}

return true;
}

public static void saveBoard(char[][] board,
List<List<String>> allBoards) {

String row = “”;
List<String> newBoard = new ArrayList<>();

for (int i = 0; i < board.length; i++) {

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] = ‘.’;
}
}
}

public static void solution(int n) {

List<List<String>> allBoards = new ArrayList<>();

char[][] board = new char[n][n];

solve(board, allBoards, 0);

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

9999999999999999

package branchsub;

import java.util.*;

public class Subset {

static int c = 0;

public static void main(String args[]) {

int w[] = new int[10];
int x[] = new int[10];

int n, d, i, sum = 0;

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.exit(0);
}

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

if(c == 0)
System.out.println(“Subset is not possible”);

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] + ” “);
}
}

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

10000000000000

package package1;

import java.util.*;

public class Hamiltonian {

static int x[] = new int[25];

static void Next_vertex(int G[][], int n, int k) {

int j;

while (true) {

x[k] = (x[k] + 1) % (n + 1);

if (x[k] == 0)
return;

if (G[x[k – 1]][x[k]] != 0) {

for (j = 1; j <= k – 1; j++) {

if (x[j] == x[k])
break;
}

if (j == k) {

if ((k < n) ||
((k == n) && (G[x[n]][x[1]] != 0)))
return;
}
}
}
}

static void H_Cycle(int G[][], int n, int k) {

int i;

while (true) {

Next_vertex(G, n, k);

if (x[k] == 0)
return;

if (k == n) {

for (i = 1; i <= n; i++)
System.out.print(x[i] + ” -> “);

System.out.println(x[1]);
}

else {

H_Cycle(G, n, k + 1);
}
}
}

public static void main(String args[]) {

int i, j, n;

int G[][] = new int[25][25];

Scanner sc = new Scanner(System.in);

System.out.println(“Enter the vertices of graph”);
n = sc.nextInt();

System.out.println(“Enter the adjacency matrix”);

for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++) {

G[i][j] = sc.nextInt();
}

x[i] = 0;
}

x[1] = 1;

System.out.println(“Hamiltonian Cycles are”);

H_Cycle(G, n, 2);

sc.close();
}
}