Graph Basics

1. Introduction: The Network of Everything

Look at a map of a subway system. Stations are connected by rail lines. Look at your Facebook account. You have friends, and those friends have friends. Look at the internet itself. Web pages link to other web pages.

All of these are Graphs. In computer science, a Graph is a non-linear data structure consisting of Vertices (nodes) and Edges (lines connecting the nodes). Unlike a Tree, which has a strict top-down hierarchy where a child has only one parent, a Graph has no rules. Any node can connect to any other node, creating complex, cyclic networks.

Mastering Graphs is essential because they model almost every complex relationship in the real world, from GPS navigation routing to artificial neural networks.

2. Core Concept: Terminology and Types

Before writing code, you must speak the language of graphs.

Graph Types

1. Undirected Graph: Edges have no direction. If A is connected to B, B is equally connected to A (like a two-way street or a Facebook friendship).
2. Directed Graph (Digraph): Edges have a direction. A points to B, but B might not point to A (like a one-way street or a Twitter follower).
3. Weighted Graph: Edges have a cost or distance associated with them. (e.g., The road from A to B takes 5 minutes).
4. Cyclic vs Acyclic: A cyclic graph contains a path that starts and ends at the same node. An Acyclic graph does not. (A Tree is mathematically defined as a "Directed Acyclic Graph" or DAG).

Graph Representation

How do we store this complex network in code? There are two primary ways:

1. Adjacency Matrix: A 2D array matrix[V][V]. If matrix[A][B] == 1, there is an edge. Best for dense graphs. Space: $O(V^2)$.
2. Adjacency List: An array (or HashMap) of Lists. adj.get(A) returns a list of all nodes connected to A. Best for sparse graphs. Space: $O(V + E)$.

In technical interviews, 95% of problems will require you to build an Adjacency List.

3. Beginner Code Example: Building an Adjacency List

Problem: You are given $N$ nodes (numbered $0$ to $N-1$) and an array of edges, where edges[i] = [u, v] represents an undirected edge between u and v. Build a data structure to represent this graph.

import java.util.ArrayList;
import java.util.List;

public class GraphRepresentation {
    public static List<List<Integer>> buildGraph(int n, int[][] edges) {
        // 1. Initialize the adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        
        // We must create an empty list for EVERY node first!
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        // 2. Populate the list
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            // Add v to u's list
            adj.get(u).add(v);
            
            // Because it is UNDIRECTED, we must also add u to v's list!
            adj.get(v).add(u); 
        }
        
        return adj;
    }
}

Complexity Analysis:

• Time Complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges. We do $O(1)$ work for each edge.
• Space Complexity: $O(V + E)$ to store all the edges in the nested lists.

4. Intermediate Code Example: Using a HashMap for String Nodes

Often, graph nodes aren't conveniently numbered 0 to N-1. They might be Strings, like Airport codes ("JFK", "LAX") or user names. We cannot use an ArrayList index for Strings. We must use a HashMap.

Problem: Build a directed graph from a list of flights [departure, destination].

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class StringGraph {
    public static Map<String, List<String>> buildFlightGraph(String[][] flights) {
        Map<String, List<String>> adj = new HashMap<>();
        
        for (String[] flight : flights) {
            String from = flight[0];
            String to = flight[1];
            
            // Initialize the list if this is the first time seeing the 'from' airport
            adj.putIfAbsent(from, new ArrayList<>());
            // It is good practice to initialize the 'to' airport as well, 
            // even if it has no outbound flights (a dead end)
            adj.putIfAbsent(to, new ArrayList<>());
            
            // Add the directed edge
            adj.get(from).add(to);
        }
        
        return adj;
    }
}

5. Advanced Code Example: Graph with Weighted Edges

If a graph has weights, we can no longer just store the destination node. We must store the (destination, weight) pair. We do this by creating a custom Edge class or using an int[] array of size 2.

import java.util.ArrayList;
import java.util.List;

public class WeightedGraph {
    // Custom class to hold the destination and the weight
    static class Edge {
        int to;
        int weight;
        
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    
    public static List<List<Edge>> buildWeightedGraph(int n, int[][] edges) {
        List<List<Edge>> adj = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            int u = edge[0]; // Source
            int v = edge[1]; // Destination
            int w = edge[2]; // Weight
            
            // Add directed weighted edge
            adj.get(u).add(new Edge(v, w));
        }
        
        return adj;
    }
}

6. Common Mistakes Beginners Make

1. Forgetting to add the reverse edge in Undirected Graphs

   • The Mistake: Writing adj.get(u).add(v) and stopping.
   • Why it's wrong: If you start a search at node v, the algorithm will think it's a dead end because you never added u to v's list. You must add both directions!

2. NullPointerException when initializing Adjacency Lists

   • The Mistake: List<List<Integer>> adj = new ArrayList<>(n); followed immediately by adj.get(u).add(v);.
   • Why it's wrong: Passing n to the ArrayList constructor only sets the internal capacity of the array. It does NOT populate it with empty lists. You must explicitly run a for loop to adj.add(new ArrayList<>()) for every vertex.

3. Confusing Vertex and Edge Complexities

   • The Mistake: Saying building a graph takes $O(N)$ time.
   • The Fix: A graph has two completely independent variables: Vertices ($V$) and Edges ($E$). A graph with 5 vertices could have 0 edges, or it could have 20 edges (fully connected). Always state Big-O in terms of both: $O(V + E)$.

7. Interview Q&A

Q1: When would you ever use an Adjacency Matrix instead of a List? Answer: You use an Adjacency Matrix (int[][] matrix) when the graph is incredibly dense (meaning almost every node is connected to every other node, so $E \approx V^2$). A matrix allows $O(1)$ lookup to instantly check if an edge exists between u and v, whereas a list requires $O(V)$ time to scan u's list. However, if $V$ is large (e.g., $10^5$), a $V \times V$ matrix will cause an OutOfMemoryError, making Adjacency Lists mandatory.

Q2: What is the Degree of a node? Answer: The degree is the number of edges connected to a node. In a directed graph, this is split into In-Degree (number of edges pointing AT the node) and Out-Degree (number of edges pointing AWAY from the node). This concept is crucial for Topological Sort algorithms.

Q3: How do you represent a Grid/Matrix as a Graph? Answer: In problems like "Number of Islands", the 2D grid IS the graph! You don't need to build an Adjacency List. Every cell (r, c) is a vertex, and its edges are implicitly its 4 neighbors: (r+1, c), (r-1, c), (r, c+1), (r, c-1).

8. Practice Problems

1. Find Center of Star Graph (LeetCode 1791)
   • Goal: Basic undirected graph logic.
2. Find the Town Judge (LeetCode 997)
   • Goal: Master In-Degree and Out-Degree concepts.
3. Number of Provinces (LeetCode 547)
   • Hint: You are given an Adjacency Matrix. Traverse it!

9. Summary

• Vertices ($V$): The entities (nodes).
• Edges ($E$): The relationships (lines).
• Adjacency List: The gold standard for storing graphs in interviews. Uses List<List<Integer>> or Map<String, List<String>>.
• Initialization Check: Never forget to instantiate the inner lists before adding edges to them.
• Undirected Rule: Always add both u -> v and v -> u.