12

 import java.util.Scanner;

public class Hamiltonian 

{

boolean found = false;

int G[][];// = new int[n + 1][n + 1];

int x[];// = new int[n + 1];

int n;

public static void main(String args[]) 

{

Hamiltonian hamiltonian = new Hamiltonian();

hamiltonian.getData();

System.out.println("\nSolution:");

hamiltonian.HamiltonianMethod(2);

hamiltonian.printNoSlnPossible();

}

public void printNoSlnPossible() 

{

if (found == false)

System.out.println("No Solution possible!");

}

public void getData() 

{

Scanner scanner = new Scanner(System.in);

System.out.println("\t\t\t\tHamiltonian Cycle");

System.out.print("\nEnter the number of the vertices: ");

// int n;

n = scanner.nextInt();

G = new int[n + 1][n + 1];

x = new int[n + 1];

System.out.print("\nIf edge between the following vertices enter 1 else 0:\n");

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

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

 {

if ((i != j) && (i < j)) 

 {

System.out.print(i + " and " + j + ": ");

G[j][i] = G[i][j] = scanner.nextInt();

 }

if (i == j)

G[i][j] = 0;

}

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

x[i] = 0;

 x[1] = 1;

scanner.close();

}

void HamiltonianMethod(int k) 

{

while (true)

 {

NextValue(k, G, x, n);

if (x[k] == 0)

return;

if (k == n) 

 {

for (int i = 1; i <= k; i++)

System.out.print(x[i] + " ");

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

System.out.println();

found = true;

return;

 } 

else

HamiltonianMethod(k + 1);

}

}

void NextValue(int k, int G[][], int x[], int n) 

{

while (true) 

{

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

if (x[k] == 0)

return;

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

{

int j;

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

if (x[k] == x[j])

break;

if (j == k)

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

return;

}

}

}

}


Comments

Post a Comment

Popular posts from this blog

9

 import java.util.Scanner; public class PrimsClass  { final static int MAX = 20; static int n; // No. of vertices of G static int cost[][]; // Cost matrix static Scanner scan = new Scanner(System.in); public static void main(String[] args)  { ReadMatrix(); Prims(); } static void ReadMatrix() { int i, j; cost = new int[MAX][MAX]; System.out.println("\n Enter the number of nodes:"); n = scan.nextInt(); System.out.println("\n Enter the adjacency matrix:\n"); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)  { cost[i][j] = scan.nextInt(); if (cost[i][j] == 0) cost[i][j] = 999; } } static void Prims()  { int visited[] = new int[10]; int ne = 1, i, j, min, a = 0, b = 0, u = 0, v = 0; int mincost = 0; visited[1] = 1; while (ne < n)   {  for (i = 1, min = 999; i <= n; i++)  for (j = 1; j <= n; j++)  if (cost[i][j] < min)  if (visited[i] != 0)   {  min = cost[i][j];  a = u = i;  b = v = j;  } ...
Read more
 PRGM::::2B import java.util.Scanner; import java.util.StringTokenizer; public class Customer   { public static void main(String[] args)   { String name; Scanner scan = new Scanner(System.in);  System.out.println("Enter Name and Date_of_Birth in the format   <Name,DD/MM/YYYY>"); name = scan.next();  // create stringTokenizer with delimiter "/" StringTokenizer st = new StringTokenizer(name, ",/");  // Count the number of tokens int count = st.countTokens(); // Print one token at a time and induce new delimiter "," for (int i = 1; i <= count && st.hasMoreTokens(); i++)   { System.out.print(st.nextToken());  if (i < count)  System.out.print(",");  }  }  }
Read more
 PRGM:::1B import java.util.*; class arrayStack  {  int arr[];  int top, max;  arrayStack(int n)   { max = n; arr = new int[max]; top = -1;  } void push(int i)  { if (top == max - 1) System.out.println("Stack Overflow"); else arr[++top] = i;  } void pop()   { if (top == -1)   { System.out.println("Stack Underflow");  }   else   { int element = arr[top--]; System.out.println("Popped Element: " + element); }  } void display()   { System.out.print("\nStack = "); if (top == -1)   { System.out.print("Empty\n"); return; } for (int i = top; i >= 0; i--)  { System.out.print(arr[i] + " "); System.out.println(); }  } class Stack { public static void main(String[] args)   { Scanner scan = new Scanner(System.in); System.out.println("Enter Size of Integer Stack "); int n = scan.nextInt(); boolean done = false; arrayStack stk = new arrayStack(n); do  { Sy...
Read more