title: Best Way to Implement an Edge Weighted Graph in Java
body: <p>First of all, I'm dealing with graphs more than 1000 edges and I'm traversing adjacency lists, as well as vertices more than 100 times per second. Therefore, I really need an efficient implementation that fits my goals.</p>
  
  <p>My vertices are integers and my edges are undirected, weighted.</p>
  
  <p>I've seen <a href="http://algs4.cs.princeton.edu/43mst/EdgeWeightedGraph.java.html" rel="nofollow noreferrer">this</a> code.<br>
  However, it models the adjacency lists using edge objects. Which means I have to spend <code>O(|adj|)</code> of time when I'd like to get the adjacents of a vertex, where <code>|adj|</code> is the cardinality of its adjacents.</p>
  
  <p>On the other hand, I'm considering to model my adjacency lists using <code>Map&lt;Integer, Double&gt;[] adj</code>.<br>
  By using this method, I would just use <code>adj[v]</code>, <code>v</code> being the vertex, and get the adjacents of the vertex to iterate over.</p>
  
  <p>The other method requires something like:</p>
  
  <pre><code>public Set&lt;Integer&gt; adj(int v) 
  {
      Set&lt;Integer&gt; adjacents = new HashSet&lt;&gt;();
      for(Edge e: adj[v])
          adjacents.add(e.other(v));
      return adjacents;
  }
  </code></pre>
  
  <p>My goals are:  </p>
  
  <ul>
  <li>I want to sort a subset of vertices by their connectivities (number of adjacents) any time I want.</li>
  <li>Also, I need to sort the adjacents of a vertex, by the weights of the edges that connect itself and its neighbors.</li>
  <li>I want to do these without using so much space that slows down the operations. Should I consider using an adjacency matrix?</li>
  </ul>