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

data-structures, graph, java, minimum-spanning-tree, sorting

Solution

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 `Edge`s 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 `Edge`s 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 :)

Problem

Original source

Related problems

• Performance: Creating an ArrayList from HashMap.values()