Prims.java

import java.io.*;
import java.util.*;
/**
* @Michael Gagala
* Implement Prim’s Algorithm
* 9 November2009
* ver 1.0
**/
class Graph {
int gph[][];
int vtx;
int edg;
void createGraph(String file) throws FileNotFoundException {
int vtx1;
int vtx2;
int wt;
try{
FileReader dataFile = new FileReader(file);
Scanner sc = new Scanner(dataFile);
vtx = sc.nextInt();
edg = sc.nextInt();
gph = new int[vtx + 1][vtx + 1];
for (int i = 1; i <= vtx; i++)
for (int j = 1; j <= vtx; j++)
gph[i][j] = 0;
for (int i = 1; i <= edg; i++) {
vtx1 = sc.nextInt();
vtx2 = sc.nextInt();
wt = sc.nextInt();
gph[vtx1][vtx2] = gph[vtx2][vtx1] = wt;
}
}
catch (FileNotFoundException e){
System.out.println(“Please check classpath, and re-enter.”);
}
}// close createGraph
void prim() {
int curpth[], pth[], visited[];
int current;
curpth = new int[vtx + 1];
pth = new int[vtx + 1];
visited = new int[vtx + 1];
for (int i = 1; i <= vtx; i++) {
curpth[i] = 255;
pth[i] = visited[i] = 0;
}
current = 1;
curpth[current] = 0;
visited[current] = 1;
int j = 1;
while (j != vtx) {
for (int i = 1; i <= vtx; i++) {
if (gph[current][i] != 0 && visited[i] != 1)
if (gph[current][i] < curpth[i]) {
curpth[i] = gph[current][i];
pth[i] = current;
}
}
int min = 255;
for (int i = 1; i <= vtx; i++) {
if (visited[i] != 1)
if (curpth[i] < min) {
min = curpth[i];
current = i;
}
}
visited[current] = 1;
j = j + 1;
}
int mincost = 0;
for (int i = 1; i <= vtx; i++)
mincost = mincost + curpth[i];
System.out.println(“\n The minimum cost: ” + mincost);
}// close prim
}// close Graph
public class prims {
public static void main(String[] args) throws FileNotFoundException {
try{
String file = args[0];
Graph g = new Graph();
g.createGraph(file);
g.prim();
}
catch (FileNotFoundException e){
System.out.println(“Please check classpath, and re-enter.”);
}
}// close main
}// close prims