使用两个列表在每条边上的权重仅为 1 和 2 的图形上的 Prim 算法
Prim's algorithm on graph with weights of only 1 and 2 on each edge using two lists
给定一个加权的、连通的、简单的无向图 G，每条边的权重仅为 1 和 2
我想这样实现Prim's algorithm：
权重为 1 或 2，因此我可以简单地将边存储在 2 个单独的列表中，一个用于权重为 1 的边，第二个用于权重为 2 的边。
为了找到权重最低的边，我只是从第一个列表中取一条，除非它是空的，在这种情况下，我从第二个列表中取一条边。
从列表中访问和删除元素的复杂度为 O(1)，因此 Prim 的算法将 运行 复杂化为 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());
}
}
I am stuck at the part of //replace-->//your code goes here//replace<--
两个 类 需要：
package il.ac.oranim.alg2016;
public class DisconnectedGraphException extends Exception {
public DisconnectedGraphException() {}
}
和
package il.ac.oranim.alg2016;
public class WrongWeightException extends Exception {
public WrongWeightException() {}
}
我也可以使用所有这些http://algs4.cs.princeton.edu/code/
can someone help me please with this part //replace-->//your code goes here//replace<--
我尝试将 This 代码复制到 //<--relpace,//replace--> 部分，然后对其进行修改，将其从使用堆更改为两个列表。
Pseudocode of Prim's algorithm
换句话说，我需要代码：
首先，使用在 O(|E|log(|V|)) 中运行的优先级队列实现正常的 Prim 算法。自己动手做，而不是照搬书上的代码。如果您不能自己实现 Prim 算法，您将无法理解如何扩展该算法。
然后，如D.W。 https://cs.stackexchange.com/questions/66498/prims-algorithm-on-graph-with-weights-of-only-1-and-2-on-each-edge 建议您可以将 ExtractMin、Remove 和 Insert 函数更改为 O(1)。
想法是您可以保留权重为 1 和 2 的边列表。如果边权重 1 的列表不为空，那么您可以通过从 O 中的列表中弹出来获得下一个要使用的最佳边（1次。如果边权重 1 的列表为空，则可以通过在 O(1) 时间内从权重 2 的列表中弹出来获得下一个最佳边。
与普通 Prim 算法的唯一不同是您需要的数据结构如下：
private class SpecialPQ {
ArrayList<NodeWeightPair> _queueWeight1 = new ArrayList<NodeWeightPair>();
ArrayList<NodeWeightPair> _queueWeight2 = new ArrayList<NodeWeightPair>();
public void insert(NodeWeightPair e) {
if (e._weight == 1) {
_queueWeight1.add(e);
}
else {
_queueWeight2.add(e);
}
}
public void remove() {
if (_queueWeight1.size() == 0) {
_queueWeight2.remove(_queueWeight2.size()-1);
}
else {
_queueWeight1.remove(_queueWeight1.size()-1);
}
}
public NodeWeightPair extractMin() {
if (_queueWeight1.size() > 0) {
return _queueWeight1.get(_queueWeight1.size()-1);
}
else {
return _queueWeight2.get(_queueWeight2.size()-1);
}
}
public boolean empty() {
return _queueWeight1.size() == 0 && _queueWeight2.size() == 0;
}
};
Normal Prim's Algorithm 使用二叉堆优先队列得到O(|E|log(|V|))。你只需要用这个更快的 SpecialPQ.
替换二进制堆优先级队列
所以本书的代码有这一行：
private IndexMinPQ<Double> pq;
您只需要将其更改为
private SpecialPQ pq;
并编译其余代码。不要从字面上复制和粘贴我的 SpecialPQ 代码。你需要很长时间才能让它与本书的代码兼容。相反，我认为您应该编写自己的 SpecialPQ，它将与您自己的 Prim 算法实现一起工作。
我在本地有一个工作示例——我自己的实现，因此它与本书的代码不兼容。如果你post你尝试实现这个，我会分享我的。
编辑：
节点权重对
private class NodeWeightPair {
private int _parent;
private int _node;
private int _weight;
public NodeWeightPair(int parent, int node, int weight) {
_node = node;
_weight = weight;
_parent = parent;
}
}
package il.ac.oranim.alg2016;
import edu.princeton.cs.algs4.*;
public class MST_12
{
private int weight; // weight of the tree
private Edge[] mstEdges; // MST edges
private boolean[] marked;// MST vertices
private Queue<Edge> queueWeight1;
private Queue<Edge> queueWeight2;
public MST_12(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 -->
queueWeight1 = new Queue<Edge>();
queueWeight2 = new Queue<Edge>();
mstEdges=new Edge[G.V()];
marked=new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run from each vertex to find
if (!marked[v]) KPrim(G,v);// minimum spanning forest
}
private void KPrim ( EdgeWeightedGraph G, int s)
{
visit(G,s);
while (!queueWeight1.isEmpty()||!queueWeight2.isEmpty()){
Edge e=null;
if (!queueWeight1.isEmpty())
{ e=queueWeight1.dequeue();}
else if (!queueWeight2.isEmpty()){e=queueWeight2.dequeue();}
int v=e.either(), w=e.other(v);
assert marked [v]||marked [w];
if(marked[v]&&marked[w]) continue;
mstEdges[s]=e;
weight+=e.weight();
if(!marked[v]) visit(G,v);// v becomes part of tree
if(!marked[w]) visit(G,w);// w becomes part of a tree
}
}
//add all edges e incident to v onto queue if the other endpoint has not yet been scanned
private void visit (EdgeWeightedGraph G, int v)
{
marked[v]=true;// add v to T
for (Edge e : G.adj(v))// for each edge e=v-w, add to queueWeight if w not already in T
{
if(!marked[e.other(v)]) {
if (e.weight()==1.0) {queueWeight1.enqueue(e);mstEdges[v]=e;}//add the smallest edge weight to the mst weight
else {queueWeight2.enqueue(e);mstEdges[v]=e;}}}
}
// <-- 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);
MST_12 mst12 = null;
try {
mst12 = new MST_12(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());
}
}
给定一个加权的、连通的、简单的无向图 G，每条边的权重仅为 1 和 2
我想这样实现Prim's algorithm：
权重为 1 或 2，因此我可以简单地将边存储在 2 个单独的列表中，一个用于权重为 1 的边，第二个用于权重为 2 的边。
为了找到权重最低的边，我只是从第一个列表中取一条，除非它是空的，在这种情况下，我从第二个列表中取一条边。
从列表中访问和删除元素的复杂度为 O(1)，因此 Prim 的算法将 运行 复杂化为 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());
}
}
I am stuck at the part of
//replace-->//your code goes here//replace<--
两个 类 需要：
package il.ac.oranim.alg2016;
public class DisconnectedGraphException extends Exception {
public DisconnectedGraphException() {}
}
和
package il.ac.oranim.alg2016;
public class WrongWeightException extends Exception {
public WrongWeightException() {}
}
我也可以使用所有这些http://algs4.cs.princeton.edu/code/
can someone help me please with this part
//replace-->//your code goes here//replace<--
我尝试将 This 代码复制到 //<--relpace,//replace--> 部分，然后对其进行修改，将其从使用堆更改为两个列表。
Pseudocode of Prim's algorithm
换句话说，我需要代码：
首先，使用在 O(|E|log(|V|)) 中运行的优先级队列实现正常的 Prim 算法。自己动手做，而不是照搬书上的代码。如果您不能自己实现 Prim 算法，您将无法理解如何扩展该算法。
然后，如D.W。 https://cs.stackexchange.com/questions/66498/prims-algorithm-on-graph-with-weights-of-only-1-and-2-on-each-edge 建议您可以将 ExtractMin、Remove 和 Insert 函数更改为 O(1)。
想法是您可以保留权重为 1 和 2 的边列表。如果边权重 1 的列表不为空，那么您可以通过从 O 中的列表中弹出来获得下一个要使用的最佳边（1次。如果边权重 1 的列表为空，则可以通过在 O(1) 时间内从权重 2 的列表中弹出来获得下一个最佳边。
与普通 Prim 算法的唯一不同是您需要的数据结构如下：
private class SpecialPQ {
ArrayList<NodeWeightPair> _queueWeight1 = new ArrayList<NodeWeightPair>();
ArrayList<NodeWeightPair> _queueWeight2 = new ArrayList<NodeWeightPair>();
public void insert(NodeWeightPair e) {
if (e._weight == 1) {
_queueWeight1.add(e);
}
else {
_queueWeight2.add(e);
}
}
public void remove() {
if (_queueWeight1.size() == 0) {
_queueWeight2.remove(_queueWeight2.size()-1);
}
else {
_queueWeight1.remove(_queueWeight1.size()-1);
}
}
public NodeWeightPair extractMin() {
if (_queueWeight1.size() > 0) {
return _queueWeight1.get(_queueWeight1.size()-1);
}
else {
return _queueWeight2.get(_queueWeight2.size()-1);
}
}
public boolean empty() {
return _queueWeight1.size() == 0 && _queueWeight2.size() == 0;
}
};
Normal Prim's Algorithm 使用二叉堆优先队列得到O(|E|log(|V|))。你只需要用这个更快的 SpecialPQ.
所以本书的代码有这一行：
private IndexMinPQ<Double> pq;
您只需要将其更改为
private SpecialPQ pq;
并编译其余代码。不要从字面上复制和粘贴我的 SpecialPQ 代码。你需要很长时间才能让它与本书的代码兼容。相反，我认为您应该编写自己的 SpecialPQ，它将与您自己的 Prim 算法实现一起工作。
我在本地有一个工作示例——我自己的实现，因此它与本书的代码不兼容。如果你post你尝试实现这个，我会分享我的。
编辑：
节点权重对
private class NodeWeightPair {
private int _parent;
private int _node;
private int _weight;
public NodeWeightPair(int parent, int node, int weight) {
_node = node;
_weight = weight;
_parent = parent;
}
}
package il.ac.oranim.alg2016;
import edu.princeton.cs.algs4.*;
public class MST_12
{
private int weight; // weight of the tree
private Edge[] mstEdges; // MST edges
private boolean[] marked;// MST vertices
private Queue<Edge> queueWeight1;
private Queue<Edge> queueWeight2;
public MST_12(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 -->
queueWeight1 = new Queue<Edge>();
queueWeight2 = new Queue<Edge>();
mstEdges=new Edge[G.V()];
marked=new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run from each vertex to find
if (!marked[v]) KPrim(G,v);// minimum spanning forest
}
private void KPrim ( EdgeWeightedGraph G, int s)
{
visit(G,s);
while (!queueWeight1.isEmpty()||!queueWeight2.isEmpty()){
Edge e=null;
if (!queueWeight1.isEmpty())
{ e=queueWeight1.dequeue();}
else if (!queueWeight2.isEmpty()){e=queueWeight2.dequeue();}
int v=e.either(), w=e.other(v);
assert marked [v]||marked [w];
if(marked[v]&&marked[w]) continue;
mstEdges[s]=e;
weight+=e.weight();
if(!marked[v]) visit(G,v);// v becomes part of tree
if(!marked[w]) visit(G,w);// w becomes part of a tree
}
}
//add all edges e incident to v onto queue if the other endpoint has not yet been scanned
private void visit (EdgeWeightedGraph G, int v)
{
marked[v]=true;// add v to T
for (Edge e : G.adj(v))// for each edge e=v-w, add to queueWeight if w not already in T
{
if(!marked[e.other(v)]) {
if (e.weight()==1.0) {queueWeight1.enqueue(e);mstEdges[v]=e;}//add the smallest edge weight to the mst weight
else {queueWeight2.enqueue(e);mstEdges[v]=e;}}}
}
// <-- 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);
MST_12 mst12 = null;
try {
mst12 = new MST_12(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());
}
}