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;

 }

if (visited[u] == 0 || visited[v] == 0) 

 {

System.out.println("Edge" + ne++ + ":(" + a + "," + b + ")" + 

"cost:" + min);

mincost += min;

visited[b] = 1;

 }

cost[a][b] = cost[b][a] = 999;

}

System.out.println("\n Minimun cost" + mincost);

}

}


Comments

Post a Comment

Popular posts from this blog

 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