Graphs are one of the most powerful data structures used in solving real-world problems like social networks, maps, recommendation systems, etc. This blog walks you through everything you need to know about Graphs in Java for both development and interview preparation.

📌 Table of Contents

  1. What is a Graph?
  2. Graph Terminologies
  3. Types of Graphs
  4. Graph Representations in Java
  5. Graph Traversal Algorithms
  6. Advanced Graph Algorithms
  7. Java Code Implementations
  8. Use Cases of Graphs
  9. Top Graph Interview Questions
  10. Conclusion

🧠 What is a Graph?

A Graph is a collection of nodes (vertices) and edges where edges represent a connection between nodes.

Formally:

A graph G is defined as a pair G = (V, E):

  • V: Set of vertices
  • E: Set of edges connecting pairs of vertices

🔑 Graph Terminologies

  • Vertex: Node in the graph
  • Edge: Connection between nodes
  • Directed Graph (Digraph): Edges have direction
  • Undirected Graph: Edges are bidirectional
  • Weighted Graph: Edges have weights
  • Cycle: A path that starts and ends at the same vertex
  • Connected Graph: There’s a path between every pair of vertices
  • Acyclic Graph: Graph with no cycles (DAG in case of Directed)

🔍 Types of Graphs

Type Description
Undirected Edges have no direction
Directed Edges point from one node to another
Weighted Edges have weights
Unweighted Edges don't have weights
Cyclic Contains cycles
Acyclic No cycles (DAGs)
Dense High number of edges
Sparse Low number of edges

🧰 Graph Representations in Java

Great! Let's dive into detailed implementations of Adjacency List and Adjacency Matrix for representing graphs in Java, including explanations and methods to add and display edges. We'll cover both undirected and directed graphs.

📋 1. Adjacency List Representation in Java

✅ Key Characteristics

  • Efficient for sparse graphs
  • Uses a Map of vertex to a list of connected vertices.
  • Space Complexity: O(V + E)

✅ Code: Undirected Graph Using Adjacency List 

import java.util.*;

public class AdjacencyListGraph {
    private Map<Integer, List<Integer>> adjList;
    private int vertices;

    public AdjacencyListGraph(int vertices) {
        this.vertices = vertices;
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new ArrayList<>());
        }
    }

    // Add edge (undirected)
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // Remove for directed graph
    }

    // Display graph
    public void printGraph() {
        for (int node : adjList.keySet()) {
            System.out.print("Vertex " + node + " -> ");
            for (int neighbor : adjList.get(node)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyListGraph graph = new AdjacencyListGraph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printGraph();
    }
}

🖨️ Sample Output 

Vertex 0 -> 1 4 
Vertex 1 -> 0 2 3 4 
Vertex 2 -> 1 3 
Vertex 3 -> 1 2 4 
Vertex 4 -> 0 1 3

🧮 2. Adjacency Matrix Representation in Java

✅ Key Characteristics

  • Great for dense graphs
  • Uses a 2D matrix where matrix[i][j] == 1 indicates an edge
  • Space Complexity: O(V²)

✅ Code: Undirected Graph Using Adjacency Matrix 

public class AdjacencyMatrixGraph {
    private int[][] adjMatrix;
    private int vertices;

    public AdjacencyMatrixGraph(int vertices) {
        this.vertices = vertices;
        adjMatrix = new int[vertices][vertices];
    }

    // Add edge (undirected)
    public void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; // Remove for directed graph
    }

    // Display matrix
    public void printMatrix() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyMatrixGraph graph = new AdjacencyMatrixGraph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printMatrix();
    }
}

🖨️ Sample Output 

Adjacency Matrix:
0 1 0 0 1 
1 0 1 1 1 
0 1 0 1 0 
0 1 1 0 1 
1 1 0 1 0

⚖️ Comparison: Adjacency List vs. Adjacency Matrix

Feature Adjacency List Adjacency Matrix
Space Complexity O(V + E) O(V²)
Ideal for Sparse graphs Dense graphs
Edge Lookup O(V) or O(logV) O(1)
Adding Edge O(1) O(1)
Removing Edge O(V) O(1)
Memory Usage Lower (sparse) High (always V²)

🌐 Graph Traversal in Java – BFS and DFS

Graphs can be traversed using two main algorithms:

  1. Breadth-First Search (BFS) – Level-order traversal using Queue (like tree BFS)
  2. Depth-First Search (DFS) – Go deep first, using Stack (iterative) or Recursion

🛠 Base Graph Structure (Adjacency List)

We'll use this class for both BFS and DFS examples:

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList;
    private int vertices;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new ArrayList<>());
        }
    }

    // Add edge (undirected)
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // Remove for directed graph
    }

    public Map<Integer, List<Integer>> getAdjList() {
        return adjList;
    }
}

🔁 BFS (Breadth-First Search)

✅ Logic

  • Use a Queue
  • Use a visited[] or Set to track visited nodes
  • Traverse level-by-level

📦 Code 

public void bfs(int start, Map<Integer, List<Integer>> adjList) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    visited.add(start);
    queue.offer(start);

    System.out.print("BFS Traversal: ");
    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print(current + " ");

        for (int neighbor : adjList.get(current)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    System.out.println();
}

📌 Time and Space Complexity

  • Time: O(V + E)
  • Space: O(V) for visited and queue

🔁 DFS (Depth-First Search) – Recursive

✅ Logic

  • Use recursion
  • Visit and go deeper into neighbors

📦 Code 

public void dfsRecursive(int current, Set<Integer> visited, Map<Integer, List<Integer>> adjList) {
    visited.add(current);
    System.out.print(current + " ");

    for (int neighbor : adjList.get(current)) {
        if (!visited.contains(neighbor)) {
            dfsRecursive(neighbor, visited, adjList);
        }
    }
}

Usage: 

System.out.print("DFS (Recursive): ");
Set<Integer> visited = new HashSet<>();
dfsRecursive(0, visited, graph.getAdjList());
System.out.println();

🔁 DFS – Iterative (Using Stack) 

public void dfsIterative(int start, Map<Integer, List<Integer>> adjList) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();

    stack.push(start);

    System.out.print("DFS (Iterative): ");
    while (!stack.isEmpty()) {
        int current = stack.pop();

        if (!visited.contains(current)) {
            visited.add(current);
            System.out.print(current + " ");

            // Push neighbors in reverse for natural left-to-right order
            List<Integer> neighbors = adjList.get(current);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    System.out.println();
}

🧪 Full Example – BFS and DFS 

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

        GraphTraversalExample gte = new GraphTraversalExample();

        gte.bfs(0, graph.getAdjList());

        System.out.print("DFS (Recursive): ");
        Set<Integer> visitedDFS = new HashSet<>();
        gte.dfsRecursive(0, visitedDFS, graph.getAdjList());
        System.out.println();

        gte.dfsIterative(0, graph.getAdjList());
    }

    public void bfs(int start, Map<Integer, List<Integer>> adjList) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.offer(start);

        System.out.print("BFS Traversal: ");
        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");
            for (int neighbor : adjList.get(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        System.out.println();
    }

    public void dfsRecursive(int current, Set<Integer> visited, Map<Integer, List<Integer>> adjList) {
        visited.add(current);
        System.out.print(current + " ");
        for (int neighbor : adjList.get(current)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited, adjList);
            }
        }
    }

    public void dfsIterative(int start, Map<Integer, List<Integer>> adjList) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        System.out.print("DFS (Iterative): ");
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited.contains(current)) {
                visited.add(current);
                System.out.print(current + " ");
                List<Integer> neighbors = adjList.get(current);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        System.out.println();
    }
}

📈 Real-World Use Cases

Traversal Use Cases
BFS Shortest path in unweighted graphs, social network suggestions
DFS Cycle detection, topological sorting, maze solving

📎 Must-Practice Interview Questions

Here are some must-do BFS/DFS questions from LeetCode & GeeksForGeeks:

BFS Questions:

DFS Questions:

🔄 Advanced Graph Algorithms

1. Topological Sort (Kahn’s Algorithm - BFS) 

void topologicalSort(Map<Integer, List<Integer>> graph, int V) {
    int[] inDegree = new int[V];
    for (List<Integer> neighbors : graph.values())
        for (int neighbor : neighbors)
            inDegree[neighbor]++;

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0)
            queue.offer(i);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (--inDegree[neighbor] == 0)
                queue.offer(neighbor);
        }
    }
}

2. Dijkstra's Algorithm 

class Pair {
    int node, dist;
    Pair(int node, int dist) {
        this.node = node;
        this.dist = dist;
    }
}

void dijkstra(int start, Map<Integer, List<Pair>> graph, int V) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist));
    pq.add(new Pair(start, 0));

    while (!pq.isEmpty()) {
        Pair current = pq.poll();
        int u = current.node;

        for (Pair neighbor : graph.get(u)) {
            int v = neighbor.node;
            int weight = neighbor.dist;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.add(new Pair(v, dist[v]));
            }
        }
    }

    System.out.println("Shortest distances: " + Arrays.toString(dist));
}

🔍 Use Cases of Graphs

Use Case Graph Application
Social Networks Nodes = Users, Edges = Friendships
Google Maps Nodes = Places, Edges = Roads
Recommender Systems Graph of items/products
Networking Routers and connections
Compilers Dependency graphs, topological sort

📚 Top Graph Interview Questions

Platform Questions
LeetCode Graph Problems
GeeksForGeeks Graph Set
InterviewBit Graph Problems
Coding Ninjas Graph Challenges

Must Practice Questions:

🧾 Conclusion

Graphs are everywhere — in tech, biology, logistics, and social systems. Knowing how to represent, traverse, and manipulate them in Java can give you a big advantage in interviews and real-world system design. Practice common problems, understand traversal deeply, and master both DFS/BFS and advanced algorithms.