Sorting edges of a graph (based on Adjacency List representation) in Java

Question

I have a graph which stores it's edges using a HashMap as follows :

HashMap<Integer,LinkedList<Node>> adj;

where Node is defined ;

class Node
{
   int number;
   int weight;
}

eg

• 0 : <1,55> -> <2,54> //node 0 is connected to node 1 with edge weight 55 and node 2 with edge weight 54
• 1 : <0,43> -> <2,44> //node 1 is connected to node 0 with edge weight 43 and node 2 with edge weight 44

I need to get a list of edges in sorted order by weight and I have no clue how to go about it. I am trying to implement Kruskal's MST.

Is it possible to sort the graph I have defined? If not please suggest a better way of storing it.

Answer 1

Let's start by creating an Edge class:

class Edge implements Comparable<Edge> { // Important: must implement Comparable. More on this later
    public Node first; // first connected node
    public Node second; // second connected node
    public int weight; // move edge weight to Edge class

    @Override
    public int compareTo(Edge e) {
        if (weight < e.weight) {
            return -1;
        } else if (weight > e.weight) {
            return 1;
        } else {
            return 0;
        }
    }
}

Because the weight variable is in the Edge class, it isn't needed in Node, so you can remove it:

class Node {
    public int number;
    // add more variables later is you need here
}

Now, for your program (if there isn't a requirement against it), I would define your list like this:

HashMap<Node, List<Edge>> adj; // use any list implementation you want

This will represent the graph like this inside your program (copied from your example):

• Node 0: Edge(Node 0, Node 1, 55), Edge(Node 0, Node 2, 54)
• Node 1: Edge(Node 1, Node 0, 43), Edge(Node 1, Node 2, 44)

To answer your question, lets find the edges sorted by edge weight:

ArrayList<Edge> sortedEdges = new ArrayList<Edge>();
for (List<Edge> connectedEdges : adj.values()) {
    sortedEdges.addAll(connectedEdges);
}
Collections.sort(sortedEdges);

This simply takes all the Edges in adj and puts them all in one list, and then sorts them according to their weight (because we made Edge extend Comparable<Edge>). As per the Javadoc on Collections.sort(), the sort() method uses merge sort, which runs in O(nlog(n)) time:

Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered.

Getting the list of all Edges by adj.values takes O(n) time (see this), so the total time complexity of getting the list of edges sorted by weight will be O(n) + O(nlog(n)) = O(nlog(n)).

So there you go. I hope this helped :)