Java Graph Implementation Example

In this example, we will write a source code example to implement Graph in Java.

A graph is a data structure for storing connected data like a network of people on a social media platform.

A graph consists of vertices and edges. A vertex represents the entity (for example, people) and an edge represents the relationship between entities (for example, a person's friendships).

Java Graph Implementation Example

Java doesn't have a default implementation of the graph data structure.

However, we can implement the graph using Java Collections.

package com.java.collections;

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

public class Graph {

	private Map<Integer, List<Integer>> adjVertices;

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

	public void addVertex(int vertex) {
		adjVertices.putIfAbsent(vertex, new ArrayList<>());
	}

	public void addEdge(int src, int dest) {
		adjVertices.get(src).add(dest);
	}

	public void dfsWithoutRecursion(int start) {
		Stack<Integer> stack = new Stack<Integer>();
		boolean[] isVisited = new boolean[adjVertices.size()];
		stack.push(start);
		while (!stack.isEmpty()) {
			int current = stack.pop();
			isVisited[current] = true;
			visit(current);
			for (int dest : adjVertices.get(current)) {
				if (!isVisited[dest])
					stack.push(dest);
			}
		}
	}

	public void dfs(int start) {
		boolean[] isVisited = new boolean[adjVertices.size()];
		dfsRecursive(start, isVisited);
	}

	private void dfsRecursive(int current, boolean[] isVisited) {
		isVisited[current] = true;
		visit(current);
		for (int dest : adjVertices.get(current)) {
			if (!isVisited[dest])
				dfsRecursive(dest, isVisited);
		}
	}

	public List<Integer> topologicalSort(int start) {
		LinkedList<Integer> result = new LinkedList<Integer>();
		boolean[] isVisited = new boolean[adjVertices.size()];
		topologicalSortRecursive(start, isVisited, result);
		return result;
	}

	private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList<Integer> result) {
		isVisited[current] = true;
		for (int dest : adjVertices.get(current)) {
			if (!isVisited[dest])
				topologicalSortRecursive(dest, isVisited, result);
		}
		result.addFirst(current);
	}

	private void visit(int value) {
		System.out.print(" " + value);
	}

	public static void main(String[] args) {
		Graph graph = new Graph();
		graph.addVertex(0);
		graph.addVertex(1);
		graph.addVertex(2);
		graph.addVertex(3);
		graph.addVertex(4);
		graph.addVertex(5);
		graph.addEdge(0, 1);
		graph.addEdge(0, 2);
		graph.addEdge(1, 3);
		graph.addEdge(2, 3);
		graph.addEdge(3, 4);
		graph.addEdge(4, 5);

		graph.dfs(0);
		System.out.println();
		graph.dfsWithoutRecursion(0);

		List<Integer> list = graph.topologicalSort(0);
		System.out.println(list);
	}
}

Output:

 0 1 3 4 5 2
 0 2 3 4 5 1[0, 2, 1, 3, 4, 5]

Learn more about Graphs at https://www.baeldung.com/java-graphs

Comments