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
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started