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
Post a Comment