Traversing Graphs
Tags: java, beginners, algorithms, datastructures
Published: 2020-01-25 22:22:43

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](https://www.baeldung.com/java-graphs) from [Kumar Chandrakant](https://www.baeldung.com/author/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. 

A graph is a collection of **Vertices** (also called Nodes or Points) and **Edges** (also called Links or Lines), where an edge is the connections between two vertices.
In a social network, each person is a vertex, and each connection between them is the edge.
![Kumar's diagram](https://www.baeldung.com/wp-content/uploads/2018/11/graph1.jpg)
<figcaption>Kumar's diagram</figcaption>

In a map, the streets are the edges and their intersections are the vertices.
![Route on map](https://thepracticaldev.s3.amazonaws.com/i/o2c3poh0ox7alolmxf4r.png)<figcaption>M&M's time!😋</figcaption>

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

```java
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:

```java
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*.

```java
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.

```java
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