More efficient implementation for 4.3.23

[dragon-dreamer]

I guess, there's a more efficient implementation for the Vyssotsky’s algorithm (4.3.23). We could sort all edges of the original graph by weight and start adding them in that order to the MST. If we find a cycle, we just skip the current edge, as it is the longest so far. Here's the implementation:

public class Vyssotsky {
    public Queue<Edge> minimumSpanningTree(EdgeWeightedGraph edgeWeightedGraph) {
        LinkedList<Edge> edges = new LinkedList<>();
        Queue<Edge> minimumSpanningTree = new LinkedList<>();
        for(Edge edge : edgeWeightedGraph.edges()) {
            edges.add(edge);
        }
        
        Collections.sort(edges);
        
        UnionFind connectedVertices = new UnionFind(edgeWeightedGraph.vertices());
        for (Edge edge : edges) {
            int v = edge.either();
            int w = edge.other(v);
            if (!connectedVertices.connected(v, w)) {
                connectedVertices.union(v, w);
                minimumSpanningTree.add(edge);
            }
        }
        
        return minimumSpanningTree;
    }
}

The time complexity should be O(E*(logE + logV)) (first logE is for sorting all edges, the second logV (or even the inverse Ackermann function) is for union-find), which is much better than O(E^2).

There's a note in the book:

This method has received less attention than the others that we consider because of the
comparative difficulty of maintaining a data structure that supports efficient implementation
of the “delete the maximum-weight edge on the cycle’’ operation.

I think, there may be an even more efficient implementation, but I don't have any more ideas for now.

[reneargento]

The algorithm you suggested works and is more efficient, but it is basically Kruskal's algorithm, and not Vyssotsky's, so I'm not sure if it is the idea of the exercise.
I added a minor improvement to the current solution here: 2436a22
Basically we don't need to search for a cycle in all vertices of the graph, a depth-first search on only one of the vertices related to the added edges in each iteration should be enough.
There may be other more efficient implementations however.

[dragon-dreamer]

I agree, my version really does look like the Kruskal's algorithm. Thank you for the improvement, it seems reasonable!

[reneargento]

By the way, since you are checking this chapter I invite you to take a look at exercise 4.3.44, Improved Boruvka if you have the time.
The way the subtrees are being merged in the repository solution is not optimal and I have been searching for a while for a more efficient solution.
This question I posted on 2017 about it still remains without an answer: https://cs.stackexchange.com/questions/85462/boruvka-mst-algorithm-using-doubly-linked-lists

[dragon-dreamer]

I've seen your solution, and I didn't have any ideas about improving its time complexity. Do you think that there exists a more optimal approach when using doubly-linked-lists?

[reneargento]

I'm not sure. The final time complexity seems to be O(E lg V), which is the expected time complexity in the exercise.
However, I was thinking there would be a more optimal way to merge the subtrees because we are not taking advantage of the doubly-linked-lists. They could be replaced with regular linked-lists and the result would be the same.

[dragon-dreamer]

Yes, it's strange that the exercise explicitly mentions doubly-linked circular lists, but it's unclear, how to utilize this property. Have you tried to directly contact Robert Sedgewick (rs@cs.princeton.edu) and ask him for help?

[reneargento]

I haven't tried yet but I will try and if I find something I will update the exercise.

[dragon-dreamer]

Thanks! Maybe it's a good idea to also write to Kevin Wayne (the second author of the book, wayne@cs.princeton.edu). Please, comment something in this issue if you get any answer.