Graph Representation

1. 1.Build Adjacency List from Edge List
   Loop edges; append v to adj[u] and u to adj[v] (for undirected)easy
2. 2.Build Directed Graph
   Loop edges; append v to adj[u] ONLYeasy
3. 3.Build Undirected Graph
   Loop edges; append both u -> v and v -> ueasy
4. 4.Build Weighted Graph
   adj[u] = append(adj[u], Edge{To: v, Weight: w})easy
5. 5.Convert Adjacency Matrix to Adjacency List
   Loop matrix[i][j]; if 1, append j to adj[i]easy
6. 6.Convert Adjacency List to Matrix
   Loop adj[u]; set matrix[u][v] = 1easy
7. 7.Clone Graph
   Adjacency List + HashMap mapping original node -> copied nodemedium
8. 8.Number of Provinces
   Adjacency Matrix traversal using visited array + DFSmedium
9. 9.Graph Valid Tree
   Build Adjacency List; verify edges == n - 1 AND graph is fully connectedmedium
10. 10.Course Schedule
    Build Directed Adjacency List + Indegree Array for Kahn's Topological Sortmedium
11. 11.Network Delay Time
    Build Weighted Adjacency List adj[u] = append(adj[u], {v, w}) for Dijkstramedium
12. 12.Reorder Routes to Make All Paths Lead to Zero
    Build Undirected Adjacency List with direction flag (1 for original, 0 for reverse)medium
13. 13.Evaluate Division
    Build Weighted Directed Map Graph map[string]map[string]float64 for query DFSmedium
14. 14.Find the Town Judge
    Track indegree and outdegree arrays: Judge has indegree == n-1 and outdegree == 0easy
15. 15.Number of Connected Components
    Convert Edge List to Adjacency List + DFS loop over unvisited nodesmedium

1. 16.Find Center of Star Graph
   Center node must appear in both first two edges edges[0] and edges[1]easy
2. 17.Redundant Connection
   Edge List + Union Find / Disjoint Set Unionmedium
3. 18.Keys and Rooms
   Adjacency List given directly as rooms array; run BFS/DFS from room 0medium
4. 19.All Paths From Source to Target
   Directed Acyclic Graph Adjacency List + Backtracking DFSmedium
5. 20.Number of Islands
   Implicit Grid Graph: 4-directional cell offset traversalmedium
6. 21.Flood Fill
   Implicit Grid Graph: cell offsets (r±1, c±1)easy
7. 22.Cheapest Flights Within K Stops
   Weighted Edge List [[u, v, w]] for Bellman-Ford / Modified BFSmedium
8. 23.Accounts Merge
   Map-based Graph connecting emails to owner name + Union Findmedium
9. 24.Minimum Height Trees
   Undirected Adjacency List + Leaf Degree trimming BFSmedium

How to Think

1. Normal sparse graph?Adjacency List
2. Need instant check: does edge u -> v exist?Adjacency Matrix
3. Input is just connections array?Edge List (Convert to Adjacency List)
4. Edges have cost / distance / time?Weighted Adjacency List
5. Grid problem?Implicit Graph (Do NOT build graph explicitly)

// 1. Build Undirected Adjacency List: O(V + E) Space
func buildUndirectedList(n int, edges [][]int) [][]int {
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u) // Both directions!
    }
    return graph
}

// 2. Build Directed Adjacency List
func buildDirectedList(n int, edges [][]int) [][]int {
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v) // u -> v ONLY!
    }
    return graph
}

// 3. Build Weighted Adjacency List
type Edge struct {
    To     int
    Weight int
}

func buildWeightedList(n int, edges [][]int) [][]Edge {
    graph := make([][]Edge, n)
    for _, edge := range edges {
        u, v, w := edge[0], edge[1], edge[2]
        graph[u] = append(graph[u], Edge{To: v, Weight: w})
    }
    return graph
}

// 4. Map-Based List for String Labels ("alice" -> ["bob"])
func buildMapGraph(edges [][]string) map[string][]string {
    graph := make(map[string][]string)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    return graph
}

Adjacency List vs Adjacency Matrix Tradeoffs

Weighted Graphs & Implicit Grid Graphs

Adjacency List   → Node -> Neighbors (O(V+E) Space, best for sparse graphs & DFS/BFS)
Adjacency Matrix → matrix[u][v] (O(V²) Space, O(1) instant direct edge check)
Undirected Graph → Add BOTH u -> v and v -> u
Directed Graph   → Add ONLY u -> v
Implicit Graph   → Calculate 4-directional grid offsets directly without explicit list

Common Interview Mistakes

Interview Rules

1. 1. Default representation choice? → Adjacency List (O(V + E) space)
2. 2. Input format in interviews? → Usually given as Edge List array [[u, v], ...]; convert before traversal
3. 3. Instant direct edge lookup required? → Adjacency Matrix (O(V²) space)
4. 4. Undirected Graph building? → Add both directions (u -> v and v -> u)
5. 5. Directed Graph building? → Add one direction only (u -> v)
6. 6. Weighted Graph building? → Store neighbor destination + weight tuple (Edge{To: v, Weight: w})
7. 7. Grid Matrix problems? → Implicit Graph (calculate 4-directional offsets directly)
8. 8. Overall Complexity → Adjacency List Space: O(V + E) | Matrix Space: O(V²)

Edge List      → Raw input connections [[u, v]]
Adjacency List → Node -> Neighbors
Matrix         → matrix[u][v]
Sparse         → List
Dense          → Matrix
Undirected     → Add both ways
Directed       → Add one way
Weighted       → Neighbor + Weight
Topological    → List + Indegree
Grid           → Implicit Graph

💡 Golden Rule: "Store the graph in the form that makes finding the neighbors needed by your algorithm simple and cheap."