Various Graph Search Algorithms Using Java

If you’ve been keeping up with my blog, I’ve made a topic regarding Binary Search Trees, but another very important topic in computer science and software engineering is in regards to Graphs.

Graphs via Wikipedia:

A graph data structure consists of a finite (and possibly mutable) set of nodes or vertices, together with a set of ordered pairs of these nodes (or, in some cases, a set of unordered pairs). These pairs are known as edges or arcs.

When interviewing for a new programming or software engineering position, it is incredibly likely that you are asked a question on this topic. Because of this, I figured it would be a good idea to go over a few of the Graph search algorithms.

The above Graph will be used throughout the rest of this article. Before we get down to business in terms of traversing / searching the Graph, let’s first figure out how to create it.

Since we know a Graph is a collection of linked nodes and values, we can conclude that the data structure looks something like the following:

public class GraphNode {

    public GraphNode[] neighbors;
    public int value;
    public boolean visited;

    public GraphNode(int v) {
        this.value = v;
        this.visited = false;
    }

}

Each GraphNode has reference to each of its neighboring nodes. We also store reference of the node’s value and whether or not we’ve visited the node before.

Now let’s create a driver class called MainDriver which will be where we create our represented Graph as well as our search algorithms. To start, lets just worry about constructing our Graph:

import java.util.*;

public class MainDriver {

    public static void main(String[] args) {

        GraphNode n1 = new GraphNode(1);
        GraphNode n2 = new GraphNode(2);
        GraphNode n3 = new GraphNode(3);
        GraphNode n4 = new GraphNode(4);
        GraphNode n5 = new GraphNode(5);
        GraphNode n6 = new GraphNode(6);
        GraphNode n7 = new GraphNode(7);

        n1.neighbors = new GraphNode[] {n2, n4, n5};
        n2.neighbors = new GraphNode[] {n1, n3, n4};
        n3.neighbors = new GraphNode[] {n2, n4, n7};
        n4.neighbors = new GraphNode[] {n1, n2, n3, n5, n6, n7};
        n5.neighbors = new GraphNode[] {n1, n4, n6};
        n6.neighbors = new GraphNode[] {n4, n5, n7};
        n7.neighbors = new GraphNode[] {n3, n4, n6};

    }

}

Of our search algorithms, the first we’re going to examine is Breadth-First Search (BFS).

Breadth-First Search via Wikipedia:

An algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.

The logic behind creating this search is as follows:

1. Create a new Java Queue of type GraphNode
2. Mark our root GraphNode as discovered and print it out
3. Add the root GraphNode into the Queue
4. Loop through the Queue infinitely until it is empty
5. Poll the head of the Queue for the GraphNode
6. Loop through all GraphNode neighbors of the polled head
7. If the neighbor has not been discovered, mark it as discovered and add it into the Queue

Now that we have it all written out, coming up with the code isn’t so difficult.

public static void BFS(GraphNode node) {

    Queue<GraphNode> queue = new LinkedList<GraphNode>();
    node.visited = true;
    queue.add(node);

    System.out.println(node.value);

    while(!queue.isEmpty()) {
        GraphNode v = queue.poll();
        for(GraphNode w : v.neighbors) {
            if(!w.visited) {
                System.out.println(w.value);
                w.visited = true;
                queue.add(w);
            }
        }
    }

}

So let’s take a look at our next searching algorithm known as Depth-First Search (DFS).

Depth-First Search via Wikipedia:

An algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

The logic behind the Depth-First Search algorithm is similar to the BFS algorithm and is as follows:

1. Create a Java Stack and push the root node to it
2. Loop until the GraphNode stack is empty
3. Pop the top GraphNode off the stack
4. If the node has not been visited, mark it so and loop through all GraphNode neighbors in reverse
5. Push each neighbor into the stack

With the logic in place, let’s check out the code to go with it:

public static void DFS(GraphNode node) {

    Stack<GraphNode> stack = new Stack<GraphNode>();
    stack.push(node);

    while(!stack.isEmpty()) {
        GraphNode v = stack.pop();
        if(!v.visited) {
            System.out.println(v.value);
            v.visited = true;
            for(int i = v.neighbors.length - 1; i >= 0; i--) {
                stack.push(v.neighbors[i]);
            }
        }
    }

}

As you can see the DFS algorithm is similar to the BFS algorithm with two major exceptions. With DFS we are using the Stack data structure instead of Queue. We are also marking GraphNode structures as visited only after popping from the stack.

If you’d prefer a sleeker version of DFS you can also solve it recursively like so:

public static void DFS(GraphNode node) {
    System.out.println(node.value);
    node.visited = true;
    for(GraphNode w : node.neighbors) {
        if(!w.visited) {
            DFS(w);
        }
    }
}

Definitely a slick way to get the job done.

Conclusion

Graph data structures can be a difficult subject to learn due to the minimal quality resources found on the internet. Regardless on the learning curve, it is still a very popular interview question and you can probably anticipate being asked about them at some point in your life. If you have experienced such a question in an interview or think you can provide a better implementation, please share in the comments as it will help readers in similar situations.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.