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!