Question: Can someone complete the GraphAlgorithm class? So that this program can run successfully.(please show me the output) public class MyGraph { public static final int

Can someone complete the GraphAlgorithm class? So that this program can run successfully.(please show me the output)
public class MyGraph { public static final int MAXSIZE = 100; public static final double BIGM = 10000000; public MyGraph(int size) { n = size; nodeStart = new Edge[MAXSIZE]; for (int i=0; i

=============================

public class Edge { public Edge(int i, int j, double c) { orig = i; dest = j; cost = c; } public int orig; public int dest; public double cost; public Edge next = null; }

=============================

public class GraphAlgorithm {

public static double totalCost(MyGraph G) {

double total = 0;

Edge loc = G.first();

while (!G.eol()) {

total = total + loc.cost;

loc = G.next();

}

return total;

}

public static void displayGraph(MyGraph G) {

Edge loc = G.first();

while (!G.eol()) {

System.out.println(loc.orig +" "+loc.dest+" "+loc.cost);

loc= G.next();

}

}

public static MyGraph prim(MyGraph G) {

int n= G.getSize();

MyGraph re=new MyGraph(n);

boolean[] in=new boolean[n];

in[0]=true;

for(int i=1; i

{

in[i]=false;

}

for(int step=1;step

{

Edge best = null;

double min=MyGraph.BIGM;

Edge e= G.first();

while(!G.eol()) {

if(in[e.orig]&& !in[e.dest]&& e.cost

{

best=e;

min=e.cost;

}

e=G.next();

}

re.insertEdge(best.orig,best.dest, best.cost);

re.next();

in[best.dest]=true;

}

return re;

}

public static MyGraph cycle(MyGraph G, int source) {

//INSERT CODE HERE

}

public static MyGraph dijkstra(MyGraph G, int source, int terminal) {

int n = G.getSize();

MyGraph result = new MyGraph(n);

double [] label = new double[n];

label[source] = 0;

int[] pred = new int[n];

pred[source] = source;

for (int i=0; i

for (int step=1; step

Edge best = null;

double min = MyGraph.BIGM;

Edge e = G.first();

while (!G.eol()) {

if (pred[e.orig] >= 0 && pred[e.dest] < 0 && label[e.orig] + e.cost < min) {

best = e;

min = label[e.orig] + e.cost;

}

e = G.next();

}

pred[best.dest] = best.orig;

label[best.dest] = label[best.orig] + best.cost;

}

int node = terminal;

while (node != pred[node]) {

result.insertEdge(pred[node], node, G.getCost(pred[node],node));

node = pred[node];

}

return result;

}

}

=====================================

 public class MSTmain { public static void main(String[] args) { MyGraph G = new MyGraph(6); G.insertEdge(0, 2, 5); G.insertEdge(2, 0, 5); G.insertEdge(1, 0, 1); G.insertEdge(0, 1, 1); G.insertEdge(0, 5, 8); G.insertEdge(5, 0, 8); G.insertEdge(1, 2, 7); G.insertEdge(2, 1, 7); G.insertEdge(1, 3, 5); G.insertEdge(3, 1, 5); G.insertEdge(2, 3, 1); G.insertEdge(3, 2, 1); G.insertEdge(1, 5, 9); G.insertEdge(5, 1, 9); G.insertEdge(3, 4, 3); G.insertEdge(4, 3, 3); G.insertEdge(4, 2, 7); G.insertEdge(2, 4, 7); G.insertEdge(5, 2, 3); G.insertEdge(2, 5, 3); G.insertEdge(4, 5, 1); G.insertEdge(5, 4, 1); GraphAlgorithm.displayGraph(G); System.out.println(); MyGraph H = GraphAlgorithm.prim(G); GraphAlgorithm.displayGraph(H); System.out.println(GraphAlgorithm.totalCost(H)); System.out.println(); MyGraph I = GraphAlgorithm.dijkstra(G,0,4); GraphAlgorithm.displayGraph(I); System.out.println(GraphAlgorithm.totalCost(I)); System.out.println(); } }

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!