względu ważonej, związany prosty nieukierunkowane wykres kz wag tylko 1 i 2 na każdej krawędziPrim na wykresie z mas tylko 1 i 2, każda krawędź stosując dwa wykazy
I zaimplementować Prim's algorithm tę sposób:
obciążniki są 1 lub 2, aby można było łatwo przechowywać krawędzie 2 oddzielnych wykazów, jeden do krawędzi o masie 1, a drugi do krawędzi o masie 2.
Aby znaleźć krawędzią przy najniższej wadze po prostu biorę jedną z pierwszej listy, chyba że jest pusta, w takim przypadku biorę przewagę z drugiej listy.
Uzyskiwanie dostępu i usuwanie elementu z listy to O (1), więc algorytm Prim będzie działał w O (V + E).
package il.ac.oranim.alg2016;
import edu.princeton.cs.algs4.*;
public class MST12 {
private int weight; // weight of the tree
private Edge[] mstEdges; // use this to store the edges of your Minimum Spanning Tree
public MST12(EdgeWeightedGraph G, int s) throws IndexOutOfBoundsException, DisconnectedGraphException, WrongWeightException {
// check that the starting vertex is in the range 0,1,...,G.V()
if (s < 0 || s >= G.V()) {
throw new IndexOutOfBoundsException();
}
// check that the input graph is connected otherwise there is no (minimum) spanning tree
if (isConnected(G) == false) {
throw new DisconnectedGraphException();
}
// check that all the weights are 1 or 2
for (Edge e : G.edges()) {
if (e.weight() != 1 && e.weight() != 2) {
throw new WrongWeightException();
}
}
this.weight = 0; // make sure you update this value
// replace -->
// your code goes here
// <-- replace
}
// returns the weight of the tree
public int weight() {
return this.weight;
}
// checks whether a graph is connected
private static boolean isConnected(EdgeWeightedGraph G) {
// create a graph of class Graph with the same edges (weights)
Graph g = new Graph(G.V());
for (Edge e : G.edges()) {
int v = e.either();
g.addEdge(v, e.other(v));
}
// compute the connected components of the graph
CC cc = new CC(g);
// return true iff there is only one connected component
return cc.count() == 1;
}
/**
* Returns the edges in a minimum spanning tree as
* an iterable of edges
*/
public Iterable<Edge> edges() {
Queue<Edge> edges = new Queue<Edge>();
for (int i = 0; i < this.mstEdges.length; i++) {
Edge e = this.mstEdges[i];
int v = e.either();
edges.enqueue(new Edge(v, e.other(v), e.weight()));
}
return edges;
}
/**
* test the computing of an MST of a graph with weights 1 and 2 only
* the first argument is the name of the file that contains the graph (graph1.txt, graph2.txt, or graph3.txt)
* you can define this argument in Run.. --> (x)=Arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
PrimMST primMST = new PrimMST(G);
MST12 mst12 = null;
try {
mst12 = new MST12(G,0);
}
catch (DisconnectedGraphException e) {
System.err.println("the input graph is not connected and hence has no (minimum) spanning tree");
}
catch (WrongWeightException e) {
System.err.println("not all weights in the input graph are 1 or 2");
}
System.out.println("Prim's MST weight = " + primMST.weight());
System.out.println("My MST's weight = " + mst12.weight());
}
}
siedzę w ramach
//replace-->//your code goes here//replace<--
dwóch klas, które potrzebne:
package il.ac.oranim.alg2016;
public class DisconnectedGraphException extends Exception {
public DisconnectedGraphException() {}
}
i
package il.ac.oranim.alg2016;
public class WrongWeightException extends Exception {
public WrongWeightException() {}
}
także mam prawo do korzystania to wszystko http://algs4.cs.princeton.edu/code/
może ktoś mi pomóc proszę z tą częścią
//replace-->//your code goes here//replace<--
Próbowałem skopiować kod This do //<--relpace,//replace--> części, a następnie do nóg to, aby go zmienić z użyciem sterty dwóch list.
Pseudocode of Prim's algorithm
Innymi słowy muszę kod to:
Co dokładnie masz problem? Czy próbowałeś zaimplementować rozwiązanie z dwiema listami opisanymi w twoim poście? Jeśli tak, co poszło nie tak? – kraskevich