Graph Fundamentals

What is a Graph?

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Unlike trees, graphs can contain cycles and have more flexible connectivity patterns.

Key Terminology

Term	Definition
Vertex (Node)	A fundamental unit of a graph
Edge	A connection between two vertices
Directed Edge	An edge with a direction (u → v)
Undirected Edge	An edge with no direction (u — v)
Weighted Edge	An edge with an associated cost/distance
Degree	Number of edges incident to a vertex
In-degree	Number of incoming edges (directed graphs)
Out-degree	Number of outgoing edges (directed graphs)
Path	A sequence of vertices connected by edges
Cycle	A path that starts and ends at the same vertex

Graph Types

Undirected Graph:          Directed Graph:
  A --- B                   A → B
  |   / |                   ↓   ↓
  |  /  |                   C → D
  C --- D

Weighted Graph:            Bipartite Graph:
  A —5— B                   Set X: {A, C}
  |     /                   Set Y: {B, D}
  3   2                     A—B, A—D, C—B, C—D
  |  /                      (edges only between sets)
  C —1— D

When to Use Graphs

• Social networks: Users as vertices, friendships as edges
• Road maps: Cities as vertices, roads as weighted edges
• Dependencies: Tasks as vertices, prerequisites as directed edges
• Web crawling: Pages as vertices, hyperlinks as directed edges

Graph Representation in Java

Adjacency List

Best for sparse graphs. Uses a map or array of lists.

import java.util.*;

public class Graph {
    private int vertices;
    private Map<Integer, List<Integer>> adjList;
    
    public Graph(int vertices) {
        this.vertices = vertices;
        this.adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new ArrayList<>());
        }
    }
    
    // Add edge for undirected graph
    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }
    
    // Add edge for directed graph
    public void addDirectedEdge(int u, int v) {
        adjList.get(u).add(v);
    }
    
    // Add weighted edge
    // Use Map<Integer, List<int[]>> where int[] = {neighbor, weight}
    
    public List<Integer> getNeighbors(int vertex) {
        return adjList.getOrDefault(vertex, new ArrayList<>());
    }
    
    public int getVertices() {
        return vertices;
    }
}

Time Complexity:

• Add edge: O(1)
• Remove edge: O(degree)
• Check if edge exists: O(degree)
• Get all neighbors: O(1)

Adjacency Matrix

Best for dense graphs. Uses a 2D array.

public class GraphMatrix {
    private int vertices;
    private int[][] matrix;
    
    public GraphMatrix(int vertices) {
        this.vertices = vertices;
        this.matrix = new int[vertices][vertices];
    }
    
    public void addEdge(int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1; // Remove for directed graph
    }
    
    public void addWeightedEdge(int u, int v, int weight) {
        matrix[u][v] = weight;
        matrix[v][u] = weight; // Remove for directed graph
    }
    
    public boolean hasEdge(int u, int v) {
        return matrix[u][v] != 0;
    }
    
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            if (matrix[vertex][i] != 0) {
                neighbors.add(i);
            }
        }
        return neighbors;
    }
}

Time Complexity:

• Add edge: O(1)
• Remove edge: O(1)
• Check if edge exists: O(1)
• Get all neighbors: O(V)

Choosing the Right Representation

Scenario	Adjacency List	Adjacency Matrix
Sparse edges (E ≪ V²)	✅ Better	❌ Wasteful
Dense edges (E ≈ V²)	❌ Overhead	✅ Better
Edge lookup needed	❌ O(degree)	✅ O(1)
Memory constrained	✅ O(V + E)	❌ O(V²)

Interview Tip

Always clarify: directed vs undirected? weighted vs unweighted? dense vs sparse? These answers determine your representation choice and algorithm selection.

Why Graph Traversal Matters

Graph traversal is the foundation of most graph algorithms. Whether finding shortest paths, detecting cycles, or solving complex puzzles, traversal patterns are the building blocks.

Two Fundamental Approaches

Graph:     0 — 1
           |   |
           2 — 3

BFS (Level by Level):       DFS (Depth First):
Level 0:  [0]               Visit 0 → 1 → 3 → 2
Level 1:  [1, 2]            (goes deep, then backtracks)
Level 2:  [3]

BFS vs DFS Comparison

Aspect	BFS	DFS
Data Structure	Queue	Stack/Recursion
Pattern	Level-by-level	Go deep, backtrack
Shortest Path	✅ (unweighted graphs)	❌
Space	O(V) worst case	O(V) worst case
Time	O(V + E)	O(V + E)
Use Case	Shortest path, level order	Cycle detection, topological sort

Basic Template: Graph Traversal Setup

// Common graph building pattern for interview problems
public class GraphTraversal {
    
    // Build graph from edge list
    public static Map<Integer, List<Integer>> buildGraph(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]); // Undirected
        }
        return graph;
    }
    
    // Build directed graph
    public static Map<Integer, List<Integer>> buildDirectedGraph(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        return graph;
    }
    
    // Build weighted graph
    public static Map<Integer, List<int[]>> buildWeightedGraph(int n, int[][] edges) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        return graph;
    }
}

Visited Array/Set Pattern

// CRITICAL: Always track visited nodes to avoid infinite loops
boolean[] visited = new boolean[n];

// Or use Set for dynamic graphs
Set<Integer> visited = new HashSet<>();

// Common mistake: forgetting to mark as visited
// This causes infinite loops in cyclic graphs!

// Correct order:
visited[node] = true;  // Mark BEFORE processing
process(node);
for (int neighbor : graph.get(node)) {
    if (!visited[neighbor]) {
        dfs(neighbor, visited);
    }
}

Common Graph Problem Patterns

1. Connected Components: Count/island problems
2. Path Finding: Shortest path, valid paths
3. Cycle Detection: Dependency resolution, deadlock detection
4. Topological Sort: Task scheduling, course prerequisites
5. Bipartite Checking: Two-coloring problems

Complexity Notes

• V = number of vertices, E = number of edges
• Both BFS and DFS: O(V + E) time, O(V) space
• Adjacency list traversal: O(V + E)
• Adjacency matrix traversal: O(V²)