java - 使用两个列表在每条边上的权重仅为 1 和 2 的图形上的 Prim 算法

Question

给定一个加权的、连通的、简单的无向图 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

换句话说，我需要为此编写代码:

Answer 1

首先，使用在 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 算法使用二叉堆优先级队列来获得 O(|E|log(|V|))。您只需用这个更快的 SpecialPQ 替换二进制堆优先级队列。

所以这本书的代码有这一行:

private IndexMinPQ<Double> pq;

你只需要把它改成

private SpecialPQ pq;

然后编译其余代码。不要直接复制和粘贴我的 SpecialPQ 代码。你需要很长时间才能让它与本书的代码兼容。相反，我认为您应该编写自己的 SpecialPQ，它将与您自己的 Prim 算法实现一起工作。

我在本地有一个工作示例 - 我自己的实现，因此它与本书的代码不兼容。如果您发布您的实现尝试，我会分享我的。

编辑:

节点权重对

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;
    }
}