2
\$\begingroup\$

My adjacency matrix looks like this, where non-zero weights denote edges.

[0, 2, 0, 0, 3]

[2, 0, 2, 4, 0]

[0, 2, 0, 3, 0]

[0, 4, 3, 0, 1]

[3, 0, 0, 1, 0]

Here's my attempt:

//nested class, only showing the relevant parts of code
class Edge implements Comparable<Edge> {
    int source;
    int destination;
    int weight;

    public Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    public String toString() {
        return source + "---" + weight + "---" + destination;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public void printPrimsMST(int[][] matrix) {
    // Start with any vertex.
    Set<Integer> visited = new HashSet<>();
    Queue<Edge> edgeQueue = new PriorityQueue<>();

    int currentNode = 0;
    visited.add(0);
    while (visited.size() < matrix.length) {

        for (int col = 0; col<matrix[currentNode].length; col++) {
            // Take all edges from this node.
            if (col == currentNode || matrix[currentNode][col] == 0) {
                //skip self as well as 0-weight edges.
                continue;
            }
            edgeQueue.add(new Edge(currentNode, col, matrix[currentNode][col]));
        }

        if (edgeQueue.isEmpty())
            return;

        //find cheapest edge to a not already visited destination.
        Edge edge = edgeQueue.remove();
        while (visited.contains(edge.destination)) {
            if (edgeQueue.isEmpty())
                return;
            edge = edgeQueue.remove();
        }

        System.out.println(edge.source + "--" + edge.weight + "--" + edge.destination);
        // Now that you've reached this edge as a destination, record it.
        currentNode = edge.destination;
        visited.add(edge.destination);
    }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Please elaborate your question. \$\endgroup\$ Nov 15 '20 at 20:30
  • \$\begingroup\$ @BillalBegueradj There's no question, this is a codereview forum and I'm asking for a code review. \$\endgroup\$ Nov 16 '20 at 17:59
1
\$\begingroup\$

I'll comment on code style, mainly.

printPrimsMST() method

It both computes the MST and prints it to System.out. This way you can't reuse it if you want to do some additional processing with its results.

So, change it to return Collection<Edge> without printing anything, and introduce a print() method that takes Collection<Edge>.

For printing, you wrote:

System.out.println(edge.source + "--" + edge.weight + "--" + edge.destination);

That's unneccessarily complex, as you defined a toString() method in the Edge class, giving exactly that format. So it's enough to use

System.out.println(edge);

Curly braces

I'd recommend to always surround blocks with curly braces (you do most of the time, but not always):

    while (visited.contains(edge.destination)) {
        if (edgeQueue.isEmpty())
            return;
        edge = edgeQueue.remove();
    }

Someone editing the code might be tempted to insert an additional instruction before returning, e.g.

    while (visited.contains(edge.destination)) {
        if (edgeQueue.isEmpty())
            doneIt = true;
            return;
        edge = edgeQueue.remove();
    }

That's a nasty trap. By indentation, it looks like a block of two statements, but it isn't (in your specific case, it's not that bad, as the compiler will flag the edge = edgeQueue.remove(); statement as unreachable, but you get the idea). So, make it a habit to always write

    while (visited.contains(edge.destination)) {
        if (edgeQueue.isEmpty()) {
            return;
        }
        edge = edgeQueue.remove();
    }

Restricting field access

class Edge implements Comparable<Edge> {
    int source;
    int destination;
    int weight;
    ...
}

The internals of a class should only be visible to the class itself. The idea of OOP is that a class defines an API visible to the outside world, and is free to decide on (and change) its inner workings. That's close to impossible if outside code directly accesses instance fields.

For that reason, make all fields private, unless you have good reason otherwise. And add only the necessary public getters and setters. And if you don't intend to change a field's value after construction of the instance, make it final as well.

You might argue that Edge is a class only meant for local use. Then make Edge a private class.

Argument checks

You are talking about undirected graphs represented as adjacency matrix. Depending on who will be calling your method, you might want to include a test whether the matrix is valid:

  • All rows must have the same length.
  • The matrix must be square.
  • The matrix must be symmetric.

If any of these conditions are violated, you should throw an IllegalArgumentException.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for all the invaluable advice. Yes, i've gotten into a poor habit of not using curlies for one-line conditionals :) I also forgot that fields are package-private by default, so its better to restrict them to be entirely private. \$\endgroup\$ Nov 16 '20 at 18:02
  • \$\begingroup\$ The idea to check the matrix for validity is also fantastic, thank you! \$\endgroup\$ Nov 16 '20 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.