title: Prim's algorithm on graph with weights of only 1 and 2 on each edge using two lists
body: <p>Given a weighted, connected, simple undirected graph G with weights of only 1 and 2 on each edge </p>
  
  <p>I want to implement <a href="https://en.wikipedia.org/wiki/Prim&#39;s_algorithm" rel="nofollow noreferrer">Prim's algorithm</a> this way:</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Accessing and deleting an element from a list is O(1) so Prim's algorithm will run in O(V+E).</p>
  
  <pre><code>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 &lt; 0 || s &gt;= 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 &amp;&amp; e.weight() != 2) {
                  throw new WrongWeightException();
              }
          }
  
          this.weight = 0; // make sure you update this value
  
          // replace --&gt;
          // your code goes here
          // &lt;-- 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&lt;Edge&gt; edges() {
          Queue&lt;Edge&gt; edges = new Queue&lt;Edge&gt;();
          for (int i = 0; i &lt; 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.. --&gt; (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());
      }
  }
  </code></pre>
  
  <blockquote>
    <p>I am stuck at the part of <code>//replace--&gt;//your code goes here//replace&lt;--</code></p>
  </blockquote>
  
  <p>two classes that needed:</p>
  
  <pre><code>package il.ac.oranim.alg2016;
  
  public class DisconnectedGraphException extends Exception {
      public DisconnectedGraphException() {}
  }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>  package il.ac.oranim.alg2016;
  
    public class WrongWeightException extends Exception {
        public WrongWeightException() {}
    }
  </code></pre>
  
  <p>Also I'm allowed to use all this <a href="http://algs4.cs.princeton.edu/code/" rel="nofollow noreferrer">http://algs4.cs.princeton.edu/code/</a></p>
  
  <blockquote>
    <p>can someone help me please with this part <code>//replace--&gt;//your code goes here//replace&lt;--</code></p>
  </blockquote>
  
  <p>I tried to copy <a href="http://algs4.cs.princeton.edu/43mst/PrimMST.java.html" rel="nofollow noreferrer">This</a> code to the <code>//&lt;--relpace,//replace--&gt;</code> part and then to feet it, to change it from using a heap to two lists.</p>
  
  <p><a href="https://cs.stackexchange.com/q/66498/44719">Pseudocode of Prim's algorithm</a></p>
  
  <p>In other words I need code for this:</p>
  
  <p><a href="https://i.stack.imgur.com/jRBvX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jRBvX.png" alt="enter image description here"></a></p>