Use for representing connections in networks, maps, social relationships, etc.

Adjacency list vs adjacency matrix?

Use adjacency list for sparse graphs (O(V+E)), matrix for dense graphs (O(V²)).

Difference between directed and undirected graphs?

Directed: A→B only, Undirected: A↔B bidirectional.

Graph Data Structure | Adjacency List· Matrix

2025년 6월 18일 · 20분 읽기 · 수정 2026년 3월 28일 Intermediate Tutorial

이 글의 핵심

Complete guide to graph data structures for coding interviews. Master adjacency list, adjacency matrix, BFS, and DFS with principles and code examples.

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

Graph: Vertices and edges, represent connections
Representation: Adjacency list (sparse), adjacency matrix (dense)
Traversal: BFS (shortest path), DFS (all paths)
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)

Keywords

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

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Complete guide to graph data structures for coding interviews. Master adjacency list, adjacency matrix, BFS, and DFS wit…

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Graph Data Structure | Adjacency List· Matrix

이 글의 핵심

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

Graph Types

2. Graph Representation

Adjacency List

Adjacency Matrix

Comparison

3. Graph Traversal

BFS (Breadth-First Search)

DFS (Depth-First Search)

4. Problem Solving

Problem 1: Count Connected Components

Problem 2: Path Exists

Problem 3: Shortest Path (Unweighted)

Problem 4: Cycle Detection

5. Practical Tips

Coding Interview Tips

BFS vs DFS Selection

Summary

Key Points

Space Complexity

Recommended Problems

Beginner

Intermediate

Advanced

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

이 글이 도움이 되셨나요?

이 글의 핵심

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

Graph Types

2. Graph Representation

Adjacency List

Adjacency Matrix

Comparison

3. Graph Traversal

BFS (Breadth-First Search)

DFS (Depth-First Search)

4. Problem Solving

Problem 1: Count Connected Components

Problem 2: Path Exists

Problem 3: Shortest Path (Unweighted)

Problem 4: Cycle Detection

5. Practical Tips

Coding Interview Tips

BFS vs DFS Selection

Summary

Key Points

Space Complexity

Recommended Problems

Beginner

Intermediate

Advanced

Related Posts

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

Related Articles (Internal Links)

Keywords Covered in This Article (Related Search Terms)

이 글이 도움이 되셨나요?