Graphs are fundamental data structures in computer science and are widely used to model complex relationships between entities. They are versatile and can represent a variety of real-world scenarios such as social networks, transportation networks, and computer networks. In this blog post, we’ll delve into some essential graph algorithms implemented in Java, covering Depth-First Search (DFS), Breadth-First Search (BFS), Dijkstra’s Shortest Path Algorithm, detecting cycles in a directed graph, and performing a topological sort.

**Understanding Graphs**

Before diving into the algorithms, let’s briefly review what graphs are. We know that data arranged in a linear manner is called linear data structures, such as Arrays, LinkedLists, Stacks, and Queues. Whereas, when data is stored non-linearly, it is referred to as non-linear data structures, such as Trees and Graphs. A graph consists of a set of vertices (nodes) and a set of edges (connections) that establish relationships between these vertices. Edges can be directed or undirected, depending on whether they have a specific direction or not. Graphs can also be weighted, where each edge has an associated weight or cost.

A **graph** is a powerful non-linear data structure consisting of two components:

**Vertices (nodes):**Represent individual entities or data points. Think of them as points on a map.**Edges:**Represent connections between vertices, indicating relationships or interactions. Edges can be bidirectional (undirected) or unidirectional (directed), like arrows showing one-way relationships.

A graph G is an ordered pair consisting of a set V of vertices and a set E of edges.

G = (V,E)

In an ordered pair, (a,b) is not equivalent to (b,a) if a ≠ b.

In an unordered pair, {a,b} equals {b,a}.

Edges:

- Directed: (u,v) i.e., u → v
- Undirected: {u,v} i.e., u — v

Example:

V = {v1, v2, v3, v4, v5, v6, v7, v8} // Set of vertices

E = { {v1, v2}, {v1, v3}, {v2, v4}, {v3, v5}, {v4, v6}, {v5, v7}, {v6, v8}, {v7, v8}, {v2, v5}, {v3, v6} }

**Graph Examples**

Consider a social network like Facebook. Users are represented as vertices, and friendships are represented as edges. If A and B are friends, we can have either a directed edge A -> B (meaning A follows B) or an undirected edge {A, B} (meaning they follow each other).

**Common Graphs Examples**

**Maps:**Represent cities as vertices and roads as edges (weighted to denote distance).**World Wide Web:**Represent web pages as vertices and hyperlinks as directed edges pointing from source pages to destination pages.**File systems:**Represent directories as vertices and subdirectory/file connections as edges.

**Graph Representations:**

**Adjacency Matrix:**Square matrix, where (i,j) reflects the edge weight between vertices i and j. Suitable for dense graphs with many edges.**Adjacency List:**Array or list of lists, where each index stores connections for a specific vertex. More efficient for sparse graphs with fewer edges.

**Implementing Graphs in Java**

To start, we’ll implement a simple graph representation in Java. We’ll use an adjacency list to store the graph, which is a list of lists where each list represents the neighbors of a particular vertex.

```
import java.util.*;
class Graph {
private int V; // Number of vertices
private LinkedList<Integer> adjList[]; // Adjacency list representation
// Constructor
Graph(int v) {
V = v;
adjList = new LinkedList[v];
for (int i = 0; i < v; ++i)
adjList[i] = new LinkedList<>();
}
// Function to add an edge to the graph
void addEdge(int v, int w) {
adjList[v].add(w);
}
// Getter for the adjacency list of a vertex
LinkedList<Integer> getAdjList(int v) {
return adjList[v];
}
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
for (int i = 0; i < graph.V; i++) {
LinkedList<Integer> list = graph.getAdjList(i);
System.out.print("Adjacency list of vertex " + i + ": ");
for (Integer node : list) {
System.out.print(node + " ");
}
System.out.println();
}
}
}
```

This `Graph`

class represents an undirected graph using an adjacency list representation. It has a constructor to initialize the graph with a given number of vertices. The `addEdge`

method adds an edge between two vertices. The `getAdjList`

method returns the adjacency list of a specified vertex.

The `main`

method demonstrates how to use the `Graph`

class by creating a graph with 4 vertices and adding some edges. Then, it prints the adjacency list of each vertex.

**Common Types of Graphs**

Here are some common types of graphs and their java implementations:

**Directed Graphs (Digraphs)**

Directed graphs, also known as digraphs, are graphs in which edges have a direction associated with them. This means that the relationship between nodes is one-way. They are used to model relationships like dependencies, flows, or hierarchical structures.

```
A
↗ ↘
B C
↘ ↗
D
```

- Vertices are represented by letters: A, B, C, D.
- Arrows indicate the direction of the edges.
- Arrows point from the source vertex to the destination vertex, representing a directed edge from the source to the destination.

**Implementation**: In Java, you can implement a directed graph using adjacency lists or adjacency matrices. Here’s a basic example of implementing a directed graph using adjacency lists:

```
import java.util.*;
class Digraph {
private int V;
private List<Integer>[] adj;
public Digraph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
```

**Undirected Graphs**

Undirected graphs are graphs in which edges do not have any direction associated with them. The relationship between nodes is bidirectional. They are used to model symmetric relationships, such as friendships in social networks or connections in a network.

```
A
/ \
/ \
B --- C
\ /
\ /
D
```

- Vertices are represented by letters: A, B, C, D.
- Edges are represented by lines connecting the vertices.
- Each line connects two vertices, representing an undirected edge between them.

**Implementation**: Similar to directed graphs, undirected graphs can be implemented using adjacency lists or adjacency matrices. Here’s a basic example of implementing an undirected graph using adjacency lists:

```
import java.util.*;
class Graph {
private int V;
private List<Integer>[] adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
```

**Weighted Graphs**

Weighted graphs are graphs in which each edge has an associated weight or cost. They are used to model scenarios where the relationship between nodes has a numerical value associated with it, such as distances between cities or costs of transportation.

```
A
2/ \4
/ \
B--5-- C
\1 3/
\ /
D
```

- Vertices are represented by letters: A, B, C, D.
- Edges are represented by lines connecting the vertices.
- Each line connecting two vertices represents an edge.
- Beside each edge, there is a number indicating the weight of that edge.
- For example, the edge between vertices A and B has a weight of 2, the edge between vertices B and D has a weight of 1, etc.

**Implementation**: Weighted graphs can be implemented similarly to undirected or directed graphs, with the addition of storing weights along with edges. Here’s an example of implementing a weighted graph using adjacency lists:

```
import java.util.*;
class WeightedGraph {
private int V;
private List<Edge>[] adj;
class Edge {
int v, w;
Edge(int v, int w) {
this.v = v;
this.w = w;
}
}
public WeightedGraph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
public void addEdge(int v, int w, int weight) {
adj[v].add(new Edge(w, weight));
adj[w].add(new Edge(v, weight)); // For undirected graphs
}
public Iterable<Edge> adj(int v) {
return adj[v];
}
}
```

**Graph Algorithms**

Now that we have our graph implementation ready, let’s explore some fundamental graph algorithms.

**Depth-First Search (DFS)** **Traversal Algorithm**

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of vertices to visit next.

```
class DFS {
// Depth-First Search traversal
void dfsUtil(int v, boolean visited[], Graph graph) {
visited[v] = true;
System.out.print(v + " ");
LinkedList<Integer> neighbors = graph.getAdjList(v);
for (Integer neighbor : neighbors) {
if (!visited[neighbor])
dfsUtil(neighbor, visited, graph);
}
}
void dfs(int v, Graph graph) {
boolean visited[] = new boolean[graph.V];
dfsUtil(v, visited, graph);
}
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
DFS dfs = new DFS();
System.out.print("Depth-First Search traversal starting from vertex 2: ");
dfs.dfs(2, graph);
}
}
```

This `DFS`

class contains methods for performing a Depth-First Search (DFS) traversal on a graph. The `dfsUtil`

method is a recursive utility function that performs DFS traversal starting from a specified vertex (`v`

). It marks the vertex as visited, prints its value, and then recursively visits its unvisited neighbors. The `dfs`

method initializes an array to track visited vertices and calls `dfsUtil`

to start the DFS traversal from a specified vertex.

The `main`

method demonstrates how to use the `DFS`

class by creating a graph with 4 vertices and adding some edges. Then, it performs a DFS traversal starting from vertex 2 and prints the traversal result.

**Breadth-First Search (BFS) Traversal Algorithm**

BFS is another traversal algorithm that explores all the neighboring nodes at the present depth prior to moving on to the nodes at the next depth level.

```
import java.util.LinkedList;
class BFS {
// Breadth-First Search traversal
void bfs(int v, Graph graph) {
boolean visited[] = new boolean[graph.V];
LinkedList<Integer> queue = new LinkedList<>();
visited[v] = true;
queue.add(v);
while (!queue.isEmpty()) {
v = queue.poll();
System.out.print(v + " ");
LinkedList<Integer> neighbors = graph.getAdjList(v);
for (Integer neighbor : neighbors) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
BFS bfs = new BFS();
System.out.print("Breadth-First Search traversal starting from vertex 2: ");
bfs.bfs(2, graph);
}
}
```

This `BFS`

class contains a method for performing a Breadth-First Search (BFS) traversal on a graph. The `bfs`

method initializes a boolean array to track visited vertices and a queue to store vertices for traversal. It starts the traversal from a specified vertex (`v`

), marks it as visited, and adds it to the queue. Then, it repeatedly dequeues vertices from the queue, prints them, and adds their unvisited neighbors to the queue.

The `main`

method demonstrates how to use the `BFS`

class by creating a graph with 4 vertices and adding some edges. Then, it performs a BFS traversal starting from vertex 2 and prints the traversal result.

**Dijkstra’s Shortest Path Algorithm**

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph. It maintains a priority queue to continuously select the vertex with the smallest distance from the source.

```
import java.util.*;
class Dijkstra {
// Dijkstra's Shortest Path Algorithm
void dijkstra(int src, Graph graph) {
int V = graph.V;
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
pq.add(src);
while (!pq.isEmpty()) {
int u = pq.poll();
LinkedList<Integer> neighbors = graph.getAdjList(u);
for (Integer v : neighbors) {
int weight = 1; // Assuming unweighted graph, modify for weighted graph
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(v);
}
}
}
// Print shortest distances
System.out.println("Shortest distances from source vertex " + src + ":");
for (int i = 0; i < V; i++) {
System.out.println("Vertex " + i + ": " + dist[i]);
}
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
Dijkstra dijkstra = new Dijkstra();
int sourceVertex = 0;
dijkstra.dijkstra(sourceVertex, graph);
}
}
```

This `Dijkstra`

class contains a method for finding the shortest path distances from a source vertex to all other vertices in a graph using Dijkstra’s algorithm. The `dijkstra`

method initializes an array to store shortest distances (`dist`

), initializes all distances to infinity except for the source vertex distance which is set to 0. It then uses a priority queue (`pq`

) to greedily select the vertex with the shortest distance and updates the distances to its neighbors if a shorter path is found. Finally, it prints the shortest distances from the source vertex to all other vertices.

The `main`

method demonstrates how to use the `Dijkstra`

class by creating a graph with 6 vertices and adding some edges. Then, it performs Dijkstra’s algorithm starting from a specified source vertex and prints the shortest distances to all other vertices.

**Detecting Cycles in a Directed Graph**

Detecting cycles in a directed graph is crucial in various applications such as deadlock detection and task scheduling. We’ll use a modified DFS approach to detect cycles.

```
class CycleDetection {
boolean isCyclicUtil(int v, boolean visited[], boolean recStack[], Graph graph) {
if (recStack[v])
return true;
if (visited[v])
return false;
visited[v] = true;
recStack[v] = true;
LinkedList<Integer> neighbors = graph.getAdjList(v);
for (Integer neighbor : neighbors) {
if (isCyclicUtil(neighbor, visited, recStack, graph))
return true;
}
recStack[v] = false;
return false;
}
boolean isCyclic(Graph graph) {
boolean visited[] = new boolean[graph.V];
boolean recStack[] = new boolean[graph.V];
for (int i = 0; i < graph.V; i++) {
if (isCyclicUtil(i, visited, recStack, graph))
return true;
}
return false;
}
public static void main(String[] args) {
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
CycleDetection cycleDetection = new CycleDetection();
if (cycleDetection.isCyclic(graph))
System.out.println("The graph contains a cycle");
else
System.out.println("The graph doesn't contain a cycle");
}
}
```

This `CycleDetection`

class contains methods to detect cycles in a graph using depth-first search (DFS). The `isCyclicUtil`

method recursively checks if there is a cycle starting from a given vertex (`v`

) by maintaining a boolean array (`recStack`

) to keep track of the vertices in the current recursion stack. If a vertex is visited and also present in the recursion stack, it indicates the presence of a cycle. The `isCyclic`

method iterates through all vertices in the graph and calls `isCyclicUtil`

for each vertex to check for cycles.

The `main`

method demonstrates how to use the `CycleDetection`

class by creating a graph with 4 vertices and adding some edges. Then, it checks if the graph contains a cycle and prints the result.

**Topological Sorting of a Graph**

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v in the ordering.

```
import java.util.*;
class TopologicalSort {
Stack<Integer> stack = new Stack<>();
void topologicalSortUtil(int v, boolean visited[], Graph graph) {
visited[v] = true;
LinkedList<Integer> neighbors = graph.getAdjList(v);
for (Integer neighbor : neighbors) {
if (!visited[neighbor])
topologicalSortUtil(neighbor, visited, graph);
}
stack.push(v);
}
void topologicalSort(Graph graph) {
int V = graph.V;
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, visited, graph);
}
// Print topological order
System.out.println("Topological order:");
while (!stack.isEmpty())
System.out.print(stack.pop() + " ");
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
TopologicalSort topologicalSort = new TopologicalSort();
topologicalSort.topologicalSort(graph);
}
}
```

This `TopologicalSort`

class contains methods to perform topological sorting on a directed acyclic graph (DAG) using depth-first search (DFS). The `topologicalSortUtil`

method recursively traverses the graph, marking visited vertices and pushing them onto a stack after visiting all of their neighbors. The `topologicalSort`

method initiates DFS traversal for each vertex and then prints the topological order by popping vertices from the stack.

The `main`

method demonstrates how to use the `TopologicalSort`

class by creating a graph with 6 vertices and adding directed edges between them. Then, it performs topological sorting and prints the topological order.

## Conclusion

In this blog post, we explored several essential graph algorithms implemented in Java, including DFS, BFS, Dijkstra’s Shortest Path Algorithm, cycle detection in directed graphs, and topological sorting. Understanding these algorithms is crucial for tackling a wide range of graph-related problems efficiently. Feel free to experiment with these implementations and explore further applications in your projects. Happy coding!