Graph Data Structure with Java

The graph data structure is a composition of nodes connected by edges. Graphs are vastly used in the real world. One very simple example is Facebook where a person is a friend of another person and so on. Graphs can also represent routes from one place to another.

A graph has nodes/vertices and is connected by the edges. To exemplify those nomenclatures, let’s see the following image:

Now that we see a node in a diagram, let’s see how we represent it in code (also remember that the following Node class will be used in the following examples):

import java.util.ArrayList;
import java.util.List;

public class Node {

  Object value;
  private List<Node> adjacentNodes = new ArrayList<>();

  public Node(Object value) {
    this.value = value;
  }

  public void addAdjacentNode(Node node) {
    this.adjacentNodes.add(node);
  }

  public List<Node> getAdjacentNodes() {
    return adjacentNodes;
  }

  public void showNodes() {
    BreathFirstSearchPrintNodes.printNodes(this);
  }

  public Object getValue() {
    return value;
  }
}

Notice that a Node in essence contains a value and its adjacent (neighbors) nodes which are represented by the adjacentNodes list.

In the constructor, we receive the value from the Node.

The addAjacentNode adds an adjacent node, also called a neighbor node.

The showNodes method will traverse and show every value from every Node by using the Breath-First-Search algorithm.

The getValue method returns the current value from the Node.

Undirected Graph

In the example of Facebook, a person is a friend of another one, therefore, this connection is unidirectional. Let’s see how this can be represented in the following image:

Notice in the graph above that Rafael is a friend of Bruno and the connection is undirected. This means that Rafael has access to Bruno’s profile and vice-versa.

Let’s see that in code in the following example. Let’s use the same Node class as above but we will explore the connect method instead:

import java.util.ArrayList;
import java.util.List;

public class Node {

  Object value;
  private List<Node> adjacentNodes = new ArrayList<>();

  // Omitted addAdjacentNode, getAdjacentNodes, showNodes, and getValue methods...
  public void connect(Node node) {
    if (this == node) throw new IllegalArgumentException("Can't connect node to itself");
    this.adjacentNodes.add(node);
    node.adjacentNodes.add(this);
  }

}

Notice in the code above that we are connecting a node to each other in the connect method. The current instance node adds the node passed via parameter and the node passed by parameter adds the current instance node to its adjacent nodes. Therefore, we have a connection from both sides between nodes.

Now, let’s populate this Node object with the same elements and print them from the above diagram:

public class UndirectedGraph {

  public static void main(String[] args) {
    Node rafaelRootNode = new Node("Rafael");
    Node brunoNode = new Node("Bruno");
    Node jamesNode = new Node("James Gosling");
    Node dukeNode = new Node("Duke");
    Node johnNode = new Node("John");

    rafaelRootNode.connect(brunoNode);
    rafaelRootNode.connect(johnNode);
    rafaelRootNode.connect(dukeNode);
    brunoNode.connect(jamesNode);

    rafaelRootNode.showNodes();
  }

}

Output:
Visited nodes: Rafael | Bruno | John | Duke | James Gosling |

Directed Graph

The graph data structure can be directional, which means that it might connect to one node but the other node might not connect back. A simple real-world example of that is when an airplane goes somewhere. The airplane will go to another city, therefore, it’s directional.

Another example is Twitter, a person can follow another one. However, the other person doesn’t need to follow back.

Let’s see how that works in the example of Twitter:

Notice in the image above that Rafael follows James Gosling, Duke, John, and Bruno. However, James Gosling, Juggy, Duke, and John don’t follow Rafael back. Rafael follows Bruno and Bruno follows back Rafael. From the node of Rafael, it’s possible to traverse through the whole graph.

Also, notice that the graph above doesn’t have cycles. Therefore, it’s an acyclic graph.

Let’s see how to represent the above graph in code:

 
public class DirectedGraph {
  public static void main(String[] args) {
    Node rafaelRootNode = new Node("Rafael");
    Node brunoNode = new Node("Bruno");
    Node jamesNode = new Node("James Gosling");
    Node juggyNode = new Node("Juggy");
    Node dukeNode = new Node("Duke");
    Node johnNode = new Node("John");

    rafaelRootNode.addAdjacentNode(brunoNode);
    brunoNode.addAdjacentNode(rafaelRootNode);
    rafaelRootNode.addAdjacentNode(jamesNode);
    rafaelRootNode.addAdjacentNode(johnNode);
    rafaelRootNode.addAdjacentNode(dukeNode);
    jamesNode.addAdjacentNode(juggyNode);

    rafaelRootNode.showNodes();
  }
}

Output:
Visited nodes: Rafael | Bruno | James Gosling | John | Duke | Juggy |

Acyclic and Cyclic Graph

A graph can be cyclic or not. This means that if there are edges connecting the graph in a cyclic way then we have a cyclic graph.

Let’s see the representation from an acyclic graph:

Representing the above acyclic graph in Java code, it’s similar to the code example from the directed graph:

public class AcyclicGraph {

  public static void main(String[] args) {
    Node dukeRootNode = new Node("Duke");
    Node mozillaNode = new Node("Mozilla");
    Node mobyDockNode = new Node("Moby Dock");
    Node juggyNode = new Node("Juggy");

    dukeRootNode.addAdjacentNode(mozillaNode);
    dukeRootNode.addAdjacentNode(mobyDockNode);
    dukeRootNode.addAdjacentNode(juggyNode);
    dukeRootNode.showNodes();
  }
}

Output:
Visited nodes: Duke | Mozilla | Moby Dock | Juggy |

When traversing through a cyclic graph, it’s necessary to check if the node was already traversed. Otherwise, an infinite looping would happen. Let’s see how a cyclic graph can be represented in the following image:

public class CyclicGraph {
  public static void main(String[] args) {
    Node dukeNode = new Node("Duke");
    Node mobyDockNode = new Node("Moby Dock");
    Node juggyNode = new Node("Juggy");

    dukeNode.addAdjacentNode(mobyDockNode);
    mobyDockNode.addAdjacentNode(juggyNode);
    juggyNode.addAdjacentNode(dukeNode);

    dukeNode.showNodes();
  }
}

Output:
Visited nodes: Duke | Moby Dock | Juggy |

Summary

The Graph data structure is highly important to be mastered by every software developer. It’s vastly used behind the scenes by frameworks, libraries, and technologies. That’s the reason why it’s vastly asked in many companies during interviews.

To recap, let’s see the important points:

• Graphs contain nodes (vertices) and connections (edges). Some real examples are friends connections from social media, and a vehicle going from one point to another.
• An adjacent or neighbor node is the direct relationship from one node to the other one.
• A graph can be directed, which means that one node can reach the other one but the other one can’t.
• A graph can be undirected, which means that the connection with another node will be bidirectional.
• A graph can be acyclic, meaning that there won’t be cycles between the nodes’ relationships.
• A graph can be cyclic, meaning that there will be cycles between the nodes’ relationships.