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.

[2026] Graph Data Structure | Adjacency List, Matrix, Traversal Complete Guide

2026년 3월 28일 · 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

아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

    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: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

    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. 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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. 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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): 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 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

[2026] 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

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

이 글의 핵심

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