Traversing Graphs

As developers, we are frequently dealing with lists, arrays, and sequence of values. But have you ever had to deal with related data, which are connected to other data? This is also known as a Graph.

These days I had to deal with it. It was scary at first.
But after reading this great article from Kumar Chandrakant, it became understandable and I felt capable of doing that.

Of course, there's a lot to learn yet, but I'm gonna show you the basics, so you have a start point to deepen your research.

In a map, the streets are the edges and their intersections are the vertices.

Using Kumar's diagram as an example, let's code.
The first step is to create a Vertex class:

public class Vertex {
    String name;
    Vertex(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null)
            return false;

        if (this == o)
            return true;

        return ((o instanceof Vertex) && (((Vertex) o).getName() == this.name));
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + name.hashCode();
        return result;
    }

    @Override
    public String toString() {
        return name;
    }
}

Basically, the vertex has only the "name" property.
But, since we will work with Java Collections, we have to override the equals, hashCode, and toString methods.

Now, it's time for Graph class:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Vertex, List<Vertex>> adjVertices;

    public Graph() {
        this.adjVertices = new HashMap<Vertex, List<Vertex>>();
    }

    void addVertex(String name) {
        adjVertices.putIfAbsent(new Vertex(name), new ArrayList<>());
    }

    void addEdge(String name1, String name2) {
        Vertex v1 = new Vertex(name1);
        Vertex v2 = new Vertex(name2);
        adjVertices.get(v1).add(v2);
        adjVertices.get(v2).add(v1);
    }

    List<Vertex> getAdjVertices(String name) {
        return adjVertices.get(new Vertex(name));
    }

    String printGraph() {
        StringBuffer sb = new StringBuffer();
        for(Vertex v : adjVertices.keySet()) {
            sb.append(v);
            sb.append(adjVertices.get(v));
            sb.append("\n");
        }
        return sb.toString();
    }
}

We are using a Map to create an adjacency list. This list will contain all relationship of each vertex.
When adding an edge, we add a vertex on the list of the related vertex.
To represent the graph, we print the adjacency list, creating a string that starts with each vertex and shows the related list in front of it.

Then we will create a Travessal class, which will contain the methods for traversing our graph. Both methods will receive a graph and a root (which will be our start point) as parameters.
There are several ways for traversing a graph, but in this article, we will only show the two most commonly used. They are known as Depth-First Traversal (DFT) and Breadth-First Traversal (BFT).
The main difference between them is that the DFT visits each child connection until the end before start visiting the siblings.
The BFT, on the other hand, visits each sibling first before visiting their children.

import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class Traversal {
    static Set<String> depthFirstTraversal(Graph graph, String root) {
        Set<String> visited = new LinkedHashSet<String>();
        Stack<String> stack = new Stack<String>();
        stack.push(root);
        while(!stack.isEmpty()) {
            String vertex = stack.pop();
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                for (Vertex v : graph.getAdjVertices(vertex)) {
                    stack.push(v.name);
                }
            }
        }
        return visited;
    }

    static Set<String> breadthFirstTraversal(Graph graph, String root) {
        Set<String> visited = new LinkedHashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.add(root);
        visited.add(root);
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            for (Vertex v : graph.getAdjVertices(vertex)) {
                if (!visited.contains(v.name)) {
                    visited.add(v.name);
                    queue.add(v.name);
                }
            }
        }
        return visited;
    }
}

Note that to DFT we use a Stack to store the vertices which will be traversed, which takes us to go deeper in each vertice.
In the BFT, we use a Queue to store the vertices, which bring us the neighbors first.

To finish, we create a graph in the main method, defining its vertices and edges and then print the adjacency list and traverse it using both kinds of traversal.

public class TraverseGraph {
    public static void main(String[] args) {

        Graph graph = new Graph();
        graph.addVertex("Bob");
        graph.addVertex("Alice");
        graph.addVertex("Mark");
        graph.addVertex("Rob");
        graph.addVertex("Maria");
        graph.addEdge("Bob", "Alice");
        graph.addEdge("Bob", "Rob");
        graph.addEdge("Alice", "Mark");
        graph.addEdge("Rob", "Mark");
        graph.addEdge("Alice", "Maria");
        graph.addEdge("Rob", "Maria");

        System.out.println(graph.printGraph());     

        System.out.println(Traversal.depthFirstTraversal(graph, "Bob"));

        System.out.println(Traversal.breadthFirstTraversal(graph, "Bob"));  

    }
}

The result will be the following:

Bob[Alice, Rob]
Rob[Bob, Mark, Maria]
Mark[Alice, Rob]
Alice[Bob, Mark, Maria]
Maria[Alice, Rob]

[Bob, Rob, Maria, Alice, Mark]
[Bob, Alice, Rob, Mark, Maria]

I hope this article clarifies the usage of Graphs.
Leave your impressions or doubts.

Sources:
[1]https://www.baeldung.com/java-graphs
[2]https://dev.to/amberjones/intro-to-graph-data-structures-abk
[3]https://dev.to/vaidehijoshi/going-broad-in-a-graph-bfs-traversal
[4]https://dev.to/jjb/part-9-learning-graphs-4859

Blog

Victor Macarios

Join Our Newsletter. No Spam, Only the good stuff.

Related