Graph Algorithms

In this lesson, we will cover three fundamental graph algorithms:

Breadth-First Search (BFS)
Depth-First Search (DFS)
Dijkstra's Algorithm

Each algorithm will be explained with Java code and detailed complexity analysis.

1. Breadth-First Search (BFS)

BFS is a traversal algorithm that explores the graph level by level, starting from the source node and visiting all its neighbors before moving to the next level.

java

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

  // Function to perform BFS traversal
  public void bfs(int startNode, LinkedList<Integer>[] adjList) {
    boolean[] visited = new boolean[adjList.length]; // To track visited nodes
    Queue<Integer> queue = new LinkedList<>(); // Queue for BFS traversal

    visited[startNode] = true; // Mark the starting node as visited
    queue.add(startNode); // Add the starting node to the queue

    while (!queue.isEmpty()) { // Continue until the queue is empty
      int currentNode = queue.poll(); // Remove and return the head of the queue
      System.out.print(currentNode + " "); // Print the node as it's visited

      // Iterate over all the adjacent nodes
      for (int neighbor : adjList[currentNode]) {
        if (!visited[neighbor]) { // Check if the neighbor has been visited
          visited[neighbor] = true; // Mark the neighbor as visited
          queue.add(neighbor); // Add the neighbor to the queue
        }
      }
    }
  }

  public static void main(String[] args) {
    int nodes = 6; // Number of nodes in the graph
    LinkedList<Integer>[] adjList = new LinkedList[nodes];

    // Initialize adjacency list
    for (int i = 0; i < nodes; i++) {
      adjList[i] = new LinkedList<>();
    }

    // Sample edges (undirected graph)
    adjList[0].add(1);
    adjList[0].add(2);
    adjList[1].add(0);
    adjList[1].add(3);
    adjList[1].add(4);
    adjList[2].add(0);
    adjList[2].add(5);
    adjList[3].add(1);
    adjList[4].add(1);
    adjList[4].add(5);
    adjList[5].add(2);
    adjList[5].add(4);

    Solution solution = new Solution();
    System.out.print("BFS Traversal starting from node 0: ");
    solution.bfs(0, adjList); // Start BFS from node 0
  }
}

Time Complexity for BFS Code

Initialization:
- Queue Initialization: Initializing the queue is .
Traversal:
- Outer While Loop:
  - The loop runs as long as the queue is not empty. Each vertex is enqueued and dequeued exactly once.
  - The poll() operation is and runs times, where V is the number of vertices.
- Inner For Loop:
  - Iterates over all adjacent nodes of currentNode. The total number of iterations across all for loops (over all vertices) is , where E is the number of edges.
  - The queue.add() operation for adding nodes to the queue is and is performed at most times.

Overall Time Complexity:

The algorithm visits each vertex and each edge exactly once, resulting in: , where V is the number of vertices and E is the number of edges in the graph.

Space Complexity for BFS Code

Visited Array:
- The visited array requires space to store the visited status for each vertex.
Queue:
- The maximum number of vertices stored in the queue at any time is in the worst case (e.g., when all vertices are at a single level in the graph).
- Space used by the queue: .

Overall Space Complexity:

The space complexity is: for the visited array and queue.

2. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking, making it useful for pathfinding and connected component analysis.

java

import java.util.LinkedList;

public class Solution {

  // Function to perform DFS traversal
  public void dfs(int node, boolean[] visited, LinkedList<Integer>[] adjList) {
    visited[node] = true; // Mark the current node as visited
    System.out.print(node + " "); // Print the node as it's visited

    // Recursively visit each adjacent node
    for (int neighbor : adjList[node]) {
      if (!visited[neighbor]) { // Check if the neighbor has been visited
        dfs(neighbor, visited, adjList); // Recursive call for DFS
      }
    }
  }

  public static void main(String[] args) {
    int nodes = 6; // Number of nodes in the graph
    LinkedList<Integer>[] adjList = new LinkedList[nodes];

    // Initialize adjacency list
    for (int i = 0; i < nodes; i++) {
      adjList[i] = new LinkedList<>();
    }

    // Sample edges (undirected graph)
    adjList[0].add(1);
    adjList[0].add(2);
    adjList[1].add(0);
    adjList[1].add(3);
    adjList[1].add(4);
    adjList[2].add(0);
    adjList[2].add(5);
    adjList[3].add(1);
    adjList[4].add(1);
    adjList[4].add(5);
    adjList[5].add(2);
    adjList[5].add(4);

    Solution solution = new Solution();
    boolean[] visited = new boolean[nodes];

    System.out.print("DFS Traversal starting from node 0: ");
    solution.dfs(0, visited, adjList); // Start DFS from node 0
  }
}

Time Complexity for DFS Code

Traversal:
- Recursive Calls:
  - Each vertex is visited once, marking it as visited and processing its adjacent vertices.
  - For each vertex node, the adjacent vertices are iterated over, resulting in a time complexity proportional to the number of edges, .
- Recursive Call Stack:
  - Each recursive call processes one vertex, and the call stack grows based on the depth of the recursion.

Overall Time Complexity:

The total time complexity for DFS is: , where V is the number of vertices and E is the number of edges in the graph.

Space Complexity for DFS Code

Visited Array:
- The visited array requires space to keep track of whether each vertex has been visited.
Recursive Call Stack:
- Depth of Recursion:
  - For a balanced graph, the maximum depth of the recursion is .
  - In the worst case (e.g., a graph that behaves like a linked list), the depth of the recursion could be .

Overall Space Complexity:

The space complexity consists of:
- for the visited array.
- for the recursion stack in the worst case.

3. Dijkstra's Algorithm

Dijkstra's Algorithm is used to find the shortest paths from a single source node to all other nodes in a weighted graph with non-negative weights.

java

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class Solution {
    // Function to perform Dijkstra's Algorithm
    public void dijkstra(int startNode, List<int[]>[] adjList) {
        int[] distances = new int[adjList.length]; // Array to store shortest distances
        Arrays.fill(distances, Integer.MAX_VALUE); // Initialize distances to infinity
        distances[startNode] = 0; // Distance to the start node is 0

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // Min-heap based on distance
        pq.add(new int[] { startNode, 0 }); // Add the start node to the priority queue

        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // Extract the node with the smallest distance
            int currentNode = current[0];
            int currentDist = current[1];

            if (currentDist > distances[currentNode]) continue; // Skip outdated paths

            // Iterate through adjacent nodes
            for (int[] neighbor : adjList[currentNode]) {
                int nextNode = neighbor[0];
                int weight = neighbor[1];
                int newDist = currentDist + weight;

                // Update the distance if a shorter path is found
                if (newDist < distances[nextNode]) {
                    distances[nextNode] = newDist;
                    pq.add(new int[] { nextNode, newDist }); // Add updated node to the queue
                }
            }
        }

        // Print the shortest distances
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Distance to node " + i + ": " + distances[i]);
        }
    }

    public static void main(String[] args) {
        int nodes = 6; // Number of nodes in the graph
        List<int[]>[] adjList = new ArrayList[nodes];

        // Initialize adjacency list
        for (int i = 0; i < nodes; i++) {
            adjList[i] = new ArrayList<>();
        }

        // Sample weighted graph edges (directed graph)
        adjList[0].add(new int[] {1, 4});
        adjList[0].add(new int[] {2, 1});
        adjList[1].add(new int[] {3, 1});
        adjList[2].add(new int[] {1, 2});
        adjList[2].add(new int[] {3, 5});
        adjList[3].add(new int[] {4, 3});
        adjList[4].add(new int[] {5, 2});
        adjList[5].add(new int[] {3, 1});

        Solution solution = new Solution();
        System.out.println("Shortest paths from node 0:");
        solution.dijkstra(0, adjList); // Run Dijkstra's algorithm from node 0
    }
}

Time Complexity for Dijkstra's Algorithm Code

Initialization:
- Distances Array: Initializing the distances array takes , where V is the number of vertices.
- Priority Queue Initialization: Adding the starting node to the priority queue is .
While Loop:
- The main loop runs as long as the priority queue is not empty. Each vertex is added to and removed from the priority queue once.
- Priority Queue Operations:
  - Polling: Removing an element from the queue takes .
  - Adding/Updating: Inserting or updating an element in the queue also takes .
- Number of Priority Queue Operations: Each vertex and its edges are processed once, resulting in operations. Here, E represents the number of edges in the graph.
For Loop (Iterating Over Adjacent Nodes):
- Each edge is relaxed at most once. The sum of iterations over all adjacent nodes across the entire graph is .
- Checking and Updating Distances: Each operation for checking and updating distances runs in , but adding to the queue takes .

Overall Time Complexity:

The total time complexity is:

This is due to the use of a priority queue and processing each edge and vertex.

Space Complexity for Dijkstra's Algorithm Code

Distances Array:
- Requires space to store the shortest distances for each vertex.
Priority Queue:
- Can hold up to elements at most, leading to space in the worst case.

Overall Space Complexity:

The space complexity consists of:
- for the distances array.
- for the priority queue.

🤖 Don't fully get this? Learn it with Claude

Stuck on Graph Algorithms? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Graph Algorithms** (DSA) and want to truly understand it. Explain Graph Algorithms from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Graph Algorithms** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Graph Algorithms** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Graph Algorithms** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Sorting Algorithms Dynamic Programming Algorithms →