1
\$\begingroup\$

Here is my approach. 1. Checking there is no cycle.(Using BFS) 2. All nodes are connected. (visited)

public static boolean isTree(int[][] adjMat) {
    int numVertex = adjMat.length;
    State[] isVisited = new State[numVertex];
    for (int i = 0; i < numVertex; i++) {
        isVisited[i] = State.UNVISITED;
    }

    // use BFS
    Queue q = new LinkedList<>();
    q.add(0);
    isVisited[0] = State.VISITING;
    while (!q.isEmpty()) {
        int current = (int) q.poll();
        if (isVisited[current] == State.VISITED) {
            return false;
        }
        isVisited[current] = State.VISITING;
        for (int i = 0; i < numVertex; i++) {
            if (adjMat[current][i] == 1) {
                q.add(i);
            }
        }
        isVisited[current] = State.VISITED;

    }
    for (int i = 0; i < numVertex; i++) {
        if (isVisited[i] == State.UNVISITED)
            return false;
    }
    return true;

}

public enum State {
    UNVISITED, VISITING, VISITED
}

Any improvements/suggestions please.

\$\endgroup\$
1
\$\begingroup\$

Task solution

Whole algorithm you created assumes node with label 0 is a root. It will give you false negative on other instances. This may be part of the assignment though, so will not be judge of that.

In case it is not, use method of gradual removal of leaves. First detect all leaves putting them in process queue. Then gradually remove those leaves, and if a neighbour of removed leaf becomes a leaf itself, add it to queue in the next round. If given graph is a tree, you should end up either with empty set of nodes, or root of the tree.

Data structures

In case it is sufficient, use byte instead of int arrays. As opposed to byte variable (1 cell = 4 bytes), byte array is actually spread to have 1 cell per 1 byte of memory. This will crank up your cache line hit chances, as more of the used information is in the cache at the same time. This pays both for input array (which you may not be able to change) but also for visited array.

Enum is all fine and dandy, but there is no good reason for enum that is used solely inside of a relatively small function. Especially when name of said enum is so generic as "state". At least make it private is you want to use it.

BFS vs DFS

BFS and DFS have the same complexity, and in this case, they would yield the same result. The difference is in performance though. In case of simple linked list queue, you create a lot of objects for starters, which is quite expensive operation in itself, that are all over the place in terms of memory, so two items in the queue will be rarely on the same cache line, and thus no hits.

For BFS, you could implement array rotational queue (limited size), where on poll you increment head and on add increment tail (both in modulus size Q, which should be power of 2 to have boost from masking instead of modulus itself). This will give you some hits from both sides of the queue.

As I mentioned, using DFS is also an option. But somewhat better, since you have array stack, fixed size again, but no modulus, shifting only one pointer. This will ensure that you operate only on one cache line, as opposed to two of them in case of queue.

The size in both cases does not need to be larger than N, number of nodes in the graph.

Pruning

When you expand, you always add a node in the queue, even though it may already be there. The thing is, if a node is inside of the queue, you already know you will encounter it twice, once marking it visited, second time finding out it is visited and terminating with false.

You can thus check whether an item is in queue (different flag) and save yourself all the computation that might come in between.

Next, the loop at the end where you are checking whether all nodes were visited at least once, it is connectivity checking. You can do that much faster, if you will introduce a counter, that is incremented (use pre-increment) every time you mark the node as visited. Then if you are checking at the end overall connectivity, you can just compare this counter to number of nodes, and if they do not match, a node was omitted. This way, you'll save N conditionals (that are well predicted, but still worse than addition), and pay for it with addition operation, which is not tied to anything else in the position of use, so it is well pipelined.

First loop can be removed as well, since removal of enum, and stating that 0 is unvisited, simple allocation initialized the array to correct values.

Conclusion

It is hard to optimize this, since complexity of DFS/BFS on adjacency matrix graph is O(N^2), so everything is kind of shaded by that.

I hope this "all over the place" text helped at least a bit.

\$\endgroup\$

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.