As the required functionality for method prim was not specified hence as per my understadning I have added definition wherein Graph has to be copied using the copy method and returned.
public class Edge { public int orig, dest; public double cost; public Edge next=null; public Edge(int i, int j, double c) { orig = i; dest = j; cost = c; } }
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(); } } //Added prim method for copying Graph G to H and returning the same public static MyGraph prim(MyGraph G) { MyGraph H = G.copy(); return H; } 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 < n; i++) if (i != source) pred[i] = -1; for (int step = 1; step < n; 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; } }
package Abc_28; 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<n; i++) { nodeStart[i] = null; } } public int getSize() { return n; } public double getCost(int i, int j) { double value = BIGM; Edge e = nodeStart[i]; while (e !=null) { if (e.dest == j) value = e.cost; e=e.next; } return value; } public void setCost(int i, int j, double c) { Edge e = nodeStart[i]; boolean found = false; while (e !=null && !found) { if (e.dest == j) { e.cost = c; found = true; } else e=e.next; } if (!found) insertEdge(i,j,c); } public void insertEdge(int i, int j, double c) { deleteEdge(i,j); Edge ins = new Edge(i,j,c); ins.next = nodeStart[i]; nodeStart[i] = ins; } public void deleteEdge(int i, int j) { boolean found = false; Edge prev = null; Edge e = nodeStart[i]; if (e != null) { if (e.dest == j) { found = true; nodeStart[i] = e.next; } else { prev = e; e = e.next; } } while (e != null && !found) { if (e.dest == j) { found = true; prev.next = e.next; } else { prev = e; e = e.next; } } } public MyGraph copy() { MyGraph result = new MyGraph(n); Edge e = first(); while (!this.eol()) { result.insertEdge(e.orig, e.dest, e.cost); e = next(); } return result; } public Edge first() { int currNode = 0; currentLoc = nodeStart[currNode]; while (currentLoc == null && currNode < n-1) { currentLoc = nodeStart[++currNode]; } return currentLoc; } public boolean eol() { return (currentLoc == null); } public Edge next() { if (!eol()) { int currNode = currentLoc.orig; currentLoc = currentLoc.next; while (currentLoc == null && currNode < n-1) { currNode++; currentLoc = nodeStart[currNode]; } return currentLoc; } else return null; } private int n; private Edge[] nodeStart; private Edge currentLoc; }
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(); } }
In the class GraphAlgorithm, insert java code for the method prim public class MyGraph { public...
Create the code for GraphAlgorithm.prim() so that the MST main routine can run properly 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);...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
To the HighArray class in the highArray.java, add a method called getMax() that returns the value of the highest key in the array, or -1 if the array is empty. Add some code in main() to exercise this method. You can assume all the keys are positive numbers. // highArray.java class HighArray { private long[] a; private int nElems; public HighArray(int max) { a = new long[max]; nElems = 0; } public boolean find(long searchKey) { int...
Assignment (to be done in Java): Person Class: public class Person extends Passenger{ private int numOffspring; public Person() { this.numOffspring = 0; } public Person (int numOffspring) { this.numOffspring = numOffspring; } public Person(String name, int birthYear, double weight, double height, char gender, int numCarryOn, int numOffspring) { super(name, birthYear, weight, height, gender, numCarryOn); if(numOffspring < 0) { this.numOffspring = 0; } this.numOffspring = numOffspring; } public int getNumOffspring() { ...
in java coorect this code & screenshoot your output ---------------------------------------------------------------------- public class UNOGame { /** * @param args the command line arguments */ public static void main(String[] args) { Scanner input=new Scanner(System.in); Scanner input2=new Scanner(System.in); UNOCard c=new UNOCard (); UNOCard D=new UNOCard (); Queue Q=new Queue(); listplayer ll=new listplayer(); System.out.println("Enter Players Name :\n Click STOP To Start Game.."); String Name = input.nextLine();...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to both classes: public void reverseThisList(), This method will reverse the lists. When testing the method: print out the original list, call the new method, then print out the list again ------------------------------------------------------------------------- //ARRAY LIST class: public class ArrayList<E> implements List<E> { /** Array of elements in this List. */ private E[] data; /** Number of elements currently in this List. */ private int size; /**...
JAVA- Complete the code by following guidelines in comments. class CircularList { private Link current; private Link prev; public CircularList() { // implement: set both current and prev to null } public boolean isEmpty() { // implement return true; } public void insert(int id) { // implement: insert the new node behind the current node } public Link delete() { // implement: delete the node referred by current return null; } public Link delete(int id) { // implement: delete the...
Consider java for fixing this code please: what i need is to insert method to be added ( please don't change the test class and any giving value in the first class ) here is the correct out put: ------------------testAddLast()---- {A} {A->B} {A->B->null} {A->B->null->C} ----------------------------- --------testSubListOfSmallerValues()---------- {} {B->B->B->A} {F->B->B->B->A->D} {F->B->B->G->B->A->M->D} ----------------------------- ------------Test lastIndexOf()----- -1 3 -1 -1 0 5 2 ----------------------------- ---------testRetainAll()--------- {} {6:Tony->6:Tony} {null->bad->null} ----------------------------- ---------------Test removeStartingAtBack--- false true {apple->null->bad->null} true {apple->null->bad} {2:Morning->3:Abby->4:Tim->5:Tom->6:Tony} ----------------------------- ---------test insertionSort()--------- {} {D} {D->E->E->F->G}...
Improve the speed of public T get(int i) by having it work backward from the end of the array if you attempt to get a member which is closer to the end than the start. This improvement will be tested through timing tests on large lists. The method should still return null if i is not a valid index. Code import java.util.Iterator; public class DLList<T> implements Iterable<T> { private static class Node<T> { public Node<T> prev, next;...
Java Programming: The following is my code: public class KWSingleLinkedList<E> { public void setSize(int size) { this.size = size; } /** Reference to list head. */ private Node<E> head = null; /** The number of items in the list */ private int size = 0; /** Add an item to the front of the list. @param item The item to be added */ public void addFirst(E...