Prim's algorithm on graph with weights of only 1 and 2 on each edge using two lists

Question

Given a weighted, connected, simple undirected graph G with weights of only 1 and 2 on each edge

I want to implement Prim's algorithm this way:

the weights are either 1 or 2, so I can simply store the edges in 2 separate lists, one for edges with weight 1, and the second for edges with weight 2.

To find the edge with lowest weight I simply take one from the first list, unless it is empty, in which case I take an edge from the second list.

Accessing and deleting an element from a list is O(1) so Prim's algorithm will run in 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<--

two classes that needed:

package il.ac.oranim.alg2016;

public class DisconnectedGraphException extends Exception {
    public DisconnectedGraphException() {}
}

and

  package il.ac.oranim.alg2016;

  public class WrongWeightException extends Exception {
      public WrongWeightException() {}
  }

Also I'm allowed to use all this http://algs4.cs.princeton.edu/code/

can someone help me please with this part //replace-->//your code goes here//replace<--

I tried to copy This code to the //<--relpace,//replace--> part and then to feet it, to change it from using a heap to two lists.

Pseudocode of Prim's algorithm

In other words I need code for this:

Answer 1

First, implement normal Prim's Algorithm with a priority queue that runs in O(|E|log(|V|)). And do it yourself instead of copying the book's code. If you can't implement Prim's Algorithm yourself, there's no way you'll understand how to extend to the algorithm.

Then, as D.W. suggested at https://cs.stackexchange.com/questions/66498/prims-algorithm-on-graph-with-weights-of-only-1-and-2-on-each-edge you can change your ExtractMin, Remove, and Insert functions to be O(1).

The idea is that you can keep a list of edges of weight 1 and 2. If the list for edge weight 1 is not empty, then you can get the next best edge to use by popping off the list in O(1) time. If the list for edge weight 1 is empty, then the next best edges can be obtained by popping off the list of weight 2 in O(1) time.

The only change from normal Prim's Algorithm is that you'll need is a data structure like this:

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 uses a binary heap priority queue to get O(|E|log(|V|)). You just have to replace the binary heap priority queue with this faster SpecialPQ.

So the book's code has this line:

private IndexMinPQ<Double> pq;

You'll just need to change that to

private SpecialPQ pq;

and get the rest of the code to compile. Don't literally copy and paste my code for SpecialPQ. It'll take you a long time get it compatible with the book's code. Instead, I think you should write your own SpecialPQ that will work with your own implementation of Prim's Algorithm.

I have a working example locally - my own implementation, so it's not compatible with the book's code. I'll share mine if you post your attempt at implementing this.

Edits:

NodeWeightPair

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