Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Modern Database Management

Authors: Jeff Hoffer, Ramesh Venkataraman, Heikki Topi

13th Edition Global Edition

1292263350, 978-1292263359

More Books

Students also viewed these Databases questions

Question

Evaluate each expression. (0.1) 3

Answered: 1 week ago

Question

What are Electrophoresis?

Answered: 1 week ago