Graph Data Structure | Adjacency List, Matrix, Traversal Complete Guide

Introduction

”Data Structure for Representing Connections”

A graph consists of nodes (vertices) and edges. It’s a more general structure than trees.

---

1. Graph Basics

Terminology

    1 --- 2
    |     |
    3 --- 4

- Vertex: 1, 2, 3, 4
- Edge: 1-2, 1-3, 2-4, 3-4
- Degree: Number of edges connected to vertex (degree of 1 = 2)
- Path: 1 → 2 → 4
- Cycle: 1 → 2 → 4 → 3 → 1

Graph Types

1) Directed Graph:

1 → 2
↓   ↓
3 → 4

2) Undirected Graph:

1 - 2
|   |
3 - 4

3) Weighted Graph:

    5
1 --- 2
|  3  |
3 --- 4
    2

---

2. Graph Representation

Adjacency List

Adjacency list stores only directly connected neighbors for each vertex. Like subway stations listing only transfer stations, it’s space-efficient for sparse graphs.

# Undirected graph
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}

# Directed graph
graph = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: []
}

# Weighted graph
graph = {
    1: [(2, 5), (3, 3)],  # (node, weight)
    2: [(1, 5), (4, 2)],
    3: [(1, 3), (4, 2)],
    4: [(2, 2), (3, 2)]
}

Adjacency Matrix

Adjacency matrix uses grid cell [i][j] to indicate if edge exists between vertices i and j. Checks edge existence in O(1) but requires O(V²) memory.

# Undirected graph (4 vertices)
graph = [
    [0, 1, 1, 0],  # Vertex 1
    [1, 0, 0, 1],  # Vertex 2
    [1, 0, 0, 1],  # Vertex 3
    [0, 1, 1, 0]   # Vertex 4
]

# Weighted graph
graph = [
    [0, 5, 3, 0],
    [5, 0, 0, 2],
    [3, 0, 0, 2],
    [0, 2, 2, 0]
]

# Check edge
if graph[0][1] > 0:
    print("1-2 connected")

Comparison

Feature	Adjacency List	Adjacency Matrix
Space	O(V+E)	O(V²)
Check edge	O(V)	O(1)
Full traversal	O(V+E)	O(V²)
Implementation	Complex	Simple
Best for	Sparse graphs	Dense graphs

---

3. Graph Traversal

BFS (Breadth-First Search)

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# Test
graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
print(bfs(graph, 1))  # [1, 2, 3, 4]

DFS (Depth-First Search)

def dfs(graph, node, visited, result):
    visited.add(node)
    result.append(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)

# Usage
visited = set()
result = []
dfs(graph, 1, visited, result)
print(result)  # [1, 2, 4, 3]

Iterative DFS (using stack):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            # Add neighbors in reverse order
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

---

4. Problem Solving

Problem 1: Count Connected Components

def count_components(n, edges):
    """
    Count connected components in undirected graph
    """
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()
    count = 0
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
    
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    
    return count

# Test
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(count_components(n, edges))  # 2

Problem 2: Path Exists

from collections import deque

def has_path(graph, start, end):
    """
    Check if path exists from start to end
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        
        if node == end:
            return True
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return False

# Test
graph = {1: [2, 3], 2: [4], 3: [], 4: []}
print(has_path(graph, 1, 4))  # True
print(has_path(graph, 1, 5))  # False

Problem 3: Shortest Path (Unweighted)

from collections import deque

def shortest_path(graph, start, end):
    """
    Find shortest path length in unweighted graph
    """
    if start == end:
        return 0
    
    visited = set([start])
    queue = deque([(start, 0)])  # (node, distance)
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # No path

# Test
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(shortest_path(graph, 1, 4))  # 2 (1→2→4)

Problem 4: Cycle Detection

def has_cycle(graph):
    """
    Detect cycle in directed graph
    """
    visited = set()
    rec_stack = set()  # Recursion stack
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # Back edge found
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    
    return False

# Test
graph = {1: [2], 2: [3], 3: [1]}  # Cycle: 1→2→3→1
print(has_cycle(graph))  # True

---

5. Practical Tips

Coding Interview Tips

# ✅ Check input format
# - Edge list → convert to adjacency list
# - 1-indexed vs 0-indexed

# ✅ Watch for directed graphs
# Undirected: graph[a].append(b), graph[b].append(a)
# Directed: graph[a].append(b) only

# ✅ Always track visited
# Prevent cycles and infinite loops

# ✅ Choose representation
# Sparse graph (E << V²): adjacency list
# Dense graph (E ≈ V²): adjacency matrix

BFS vs DFS Selection

Use Case	Algorithm	Reason
Shortest path	BFS	Level-order guarantees shortest
All paths	DFS	Explores deeply
Connected components	Either	Both work
Cycle detection	DFS	Track recursion stack
Topological sort	DFS	Postorder gives reverse topo

---

Summary

Key Points

1. Graph: Vertices and edges, represent connections
2. Representation: Adjacency list (sparse), adjacency matrix (dense)
3. Traversal: BFS (shortest path), DFS (all paths)
4. Time Complexity: O(V+E)

Space Complexity

Representation	Space	Best For
Adjacency List	O(V+E)	Sparse graphs (social networks)
Adjacency Matrix	O(V²)	Dense graphs (complete graphs)

---

Recommended Problems

Beginner

• LeetCode 200: Number of Islands
• LeetCode 733: Flood Fill
• LeetCode 997: Find the Town Judge

Intermediate

• LeetCode 133: Clone Graph
• LeetCode 207: Course Schedule
• LeetCode 323: Number of Connected Components

Advanced

• LeetCode 269: Alien Dictionary
• LeetCode 310: Minimum Height Trees
• LeetCode 332: Reconstruct Itinerary

---

Related Posts

• Tree Data Structure | Complete Guide
• BFS and DFS | Graph Traversal Algorithms
• Arrays and Lists | Essential Data Structures
• Stack and Queue | LIFO and FIFO

---

Keywords

Graph, Data Structure, Adjacency List, Adjacency Matrix, BFS, DFS, Graph Traversal, Shortest Path, Cycle Detection, Connected Components, Coding Interview, Algorithm