그래프 & 알고리즘 정리

목차

1. 그래프 기본 개념
2. 그래프 종류
3. 그래프 표현 방식
4. BFS / DFS
5. 위상 정렬
6. B-Tree
7. 트라이 (Trie)
8. 최단 경로 알고리즘
9. 최소 신장 트리

---

1. 그래프 기본 개념

그래프란?

• 정의: 정점(Vertex)과 간선(Edge)으로 구성된 비선형 자료구조
• 실생활 예시: 지도의 도시와 도로, SNS의 친구 관계, 웹페이지의 링크 구조

기본 용어

• 정점(Vertex/Node): 그래프의 기본 단위, 데이터를 저장하는 지점
• 간선(Edge/Arc): 두 정점을 연결하는 선
• 인접(Adjacent): 두 정점이 간선으로 직접 연결된 관계
• 차수(Degree): 한 정점에 연결된 간선의 수
• 경로(Path): 한 정점에서 다른 정점까지의 정점과 간선의 순서
• 사이클(Cycle): 시작점과 끝점이 같은 경로

시각적 표현

그래프 예시:
     A ─── B
     │     │
     │     │
     C ─── D ─── E

정점: {A, B, C, D, E}
간선: {(A,B), (A,C), (B,D), (C,D), (D,E)}

---

2. 그래프 종류

1. 방향성에 따른 분류

무방향 그래프 (Undirected Graph)

• 특징: 간선에 방향이 없음
• 표현: (A, B) = (B, A)
• 예시: 친구 관계, 도로망

무방향 그래프:
A ─── B
│     │
C ─── D

방향 그래프 (Directed Graph/Digraph)

• 특징: 간선에 방향이 있음
• 표현: A → B ≠ B → A
• 예시: 웹페이지 링크, 일방통행 도로

방향 그래프:
A ──→ B
│     │
↓     ↓
C ←── D

2. 가중치에 따른 분류

가중 그래프 (Weighted Graph)

• 특징: 간선에 가중치(비용, 거리 등)가 있음
• 활용: 최단 경로 찾기, 네트워크 분석

가중 그래프:
     5      3
A ─────── B ─────── C
│         │         │
│2        │4        │1
│         │         │
D ─────── E ─────── F
     7      6

3. 특수한 그래프 유형

완전 그래프 (Complete Graph)

• 모든 정점이 서로 연결된 그래프
• n개 정점의 완전 그래프: n(n-1)/2 개의 간선

트리 (Tree)

• 사이클이 없는 연결된 무방향 그래프
• n개 정점, n-1개 간선

이분 그래프 (Bipartite Graph)

• 정점을 두 그룹으로 나눌 수 있는 그래프
• 같은 그룹 내 정점들은 서로 연결되지 않음

---

3. 그래프 표현 방식

1. 인접 행렬 (Adjacency Matrix)

개념

• 정의: 2차원 배열을 사용하여 그래프를 표현
• 크기: n×n (n: 정점의 수)
• 값: matrix[i][j] = 정점 i와 j 사이의 간선 정보

특징

장점:

• 간선 존재 여부를 O(1)에 확인 가능
• 구현이 간단
• 밀집 그래프에 효율적

단점:

• 공간 복잡도: O(V²)
• 희소 그래프에서 메모리 낭비

표현 방법

무방향 그래프:     인접 행렬:
A ─── B           A B C D
│     │       A [ 0 1 1 0 ]
C ─── D       B [ 1 0 0 1 ]
              C [ 1 0 0 1 ]
              D [ 0 1 1 0 ]

가중 그래프:       인접 행렬:
A ─5─ B           A B C
│     │       A [ 0 5 2 ]
2     3       B [ 5 0 3 ]
│     │       C [ 2 3 0 ]
C ─3─ ┘

Python 구현

class AdjacencyMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, u, v, weight=1):
        """간선 추가"""
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight  # 무방향 그래프
    
    def has_edge(self, u, v):
        """간선 존재 확인"""
        return self.matrix[u][v] != 0
    
    def get_neighbors(self, vertex):
        """인접 정점들 반환"""
        neighbors = []
        for i in range(self.num_vertices):
            if self.matrix[vertex][i] != 0:
                neighbors.append(i)
        return neighbors

2. 인접 리스트 (Adjacency List)

개념

• 정의: 각 정점마다 연결된 정점들의 리스트를 저장
• 구조: 배열 + 연결리스트 또는 딕셔너리

특징

장점:

• 공간 복잡도: O(V + E)
• 희소 그래프에 효율적
• 정점의 모든 인접 정점을 빠르게 순회

단점:

• 특정 간선 존재 확인: O(degree)
• 구현이 상대적으로 복잡

표현 방법

그래프:           인접 리스트:
A ─── B           A: [B, C]
│     │           B: [A, D]
C ─── D           C: [A, D]
                  D: [B, C]

가중 그래프:       인접 리스트:
A ─5─ B           A: [(B,5), (C,2)]
│     │           B: [(A,5), (C,3)]
2     3           C: [(A,2), (B,3)]
│     │
C ─3─ ┘

Python 구현

from collections import defaultdict

class AdjacencyList:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, weight=1):
        """간선 추가"""
        self.graph[u].append((v, weight))
        self.graph[v].append((u, weight))  # 무방향 그래프
    
    def get_neighbors(self, vertex):
        """인접 정점들 반환"""
        return self.graph[vertex]
    
    def has_edge(self, u, v):
        """간선 존재 확인"""
        return any(neighbor == v for neighbor, _ in self.graph[u])

인접 행렬 vs 인접 리스트 비교

연산	인접 행렬	인접 리스트
공간 복잡도	O(V²)	O(V + E)
간선 추가	O(1)	O(1)
간선 제거	O(1)	O(degree)
간선 확인	O(1)	O(degree)
정점의 차수	O(V)	O(1)
모든 간선 순회	O(V²)	O(V + E)

---

4. BFS / DFS

너비 우선 탐색 (BFS - Breadth First Search)

개념

• 정의: 시작 정점에서 가까운 정점부터 차례대로 탐색
• 특징: 큐(Queue)를 사용한 레벨 순회
• 시간 복잡도: O(V + E)

동작 과정

그래프:     BFS 탐색 순서:
   A        1. A (시작)
  / \       2. B, C (A의 인접 정점)
 B   C      3. D, E (B의 인접 정점)
/|   |      4. F (E의 인접 정점)
D E   F     

활용

• 최단 경로 찾기 (가중치가 없는 그래프)
• 연결 요소 찾기
• 레벨별 탐색

Python 구현

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            
            # 인접 정점들을 큐에 추가
            for neighbor, _ in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
    
    return result

깊이 우선 탐색 (DFS - Depth First Search)

개념

• 정의: 한 방향으로 깊숙이 탐색한 후 다른 방향으로 탐색
• 특징: 스택(Stack) 또는 재귀를 사용
• 시간 복잡도: O(V + E)

동작 과정

그래프:     DFS 탐색 순서:
   A        1. A (시작)
  / \       2. B (A의 첫 번째 인접 정점)
 B   C      3. D (B의 첫 번째 인접 정점)
/|   |      4. E (B의 두 번째 인접 정점)
D E   F     5. C, F (백트래킹 후 탐색)

활용

• 사이클 검출
• 위상 정렬
• 강연결 요소 찾기
• 미로 찾기

Python 구현

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    result = [start]
    
    for neighbor, _ in graph[start]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))
    
    return result

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            
            # 인접 정점들을 스택에 추가 (역순으로 추가)
            for neighbor, _ in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

BFS vs DFS 비교

특성	BFS	DFS
자료구조	큐 (Queue)	스택 (Stack)
메모리 사용	많음	적음
최단 경로	보장	보장 안함
완전성	완전함	완전함
최적성	최적	비최적

---

5. 위상 정렬

개념

• 정의: 방향 그래프에서 정점들을 방향에 거스르지 않게 일렬로 나열
• 전제 조건: DAG (Directed Acyclic Graph)
• 시간 복잡도: O(V + E)

활용 사례

• 과목 수강 순서: 선수과목이 있는 강의 계획
• 작업 스케줄링: 의존성이 있는 작업들의 순서
• 컴파일 순서: 모듈 간 의존성

시각적 예시

수강 과목 의존성:
수학1 ──→ 수학2 ──→ 미적분
  │         │
  ↓         ↓
물리1 ──→ 물리2

위상 정렬 결과: 수학1 → 물리1 → 수학2 → 물리2 → 미적분
또는:          수학1 → 수학2 → 물리1 → 물리2 → 미적분

구현 방법

1. 칸의 알고리즘 (Kahn's Algorithm)

from collections import deque, defaultdict

def topological_sort_kahn(graph):
    # 진입 차수 계산
    in_degree = defaultdict(int)
    for vertex in graph:
        for neighbor, _ in graph[vertex]:
            in_degree[neighbor] += 1
    
    # 진입 차수가 0인 정점들을 큐에 추가
    queue = deque([v for v in graph if in_degree[v] == 0])
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        # 인접 정점들의 진입 차수 감소
        for neighbor, _ in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 사이클 검사
    if len(result) != len(graph):
        return None  # 사이클 존재
    
    return result

2. DFS 기반 알고리즘

def topological_sort_dfs(graph):
    visited = set()
    temp_visited = set()
    result = []
    
    def dfs(vertex):
        if vertex in temp_visited:
            return False  # 사이클 발견
        if vertex in visited:
            return True
        
        temp_visited.add(vertex)
        
        for neighbor, _ in graph[vertex]:
            if not dfs(neighbor):
                return False
        
        temp_visited.remove(vertex)
        visited.add(vertex)
        result.append(vertex)
        return True
    
    for vertex in graph:
        if vertex not in visited:
            if not dfs(vertex):
                return None  # 사이클 존재
    
    return result[::-1]  # 역순으로 반환

---

6. B-Tree

개념

• 정의: 균형잡힌 다진 탐색 트리
• 특징: 모든 리프 노드가 같은 레벨에 위치
• 차수 m: 각 노드가 최대 m개의 자식을 가질 수 있음

B-Tree의 성질

1. 루트를 제외한 모든 노드는 최소 ⌈m/2⌉-1개의 키를 가짐
2. 모든 노드는 최대 m-1개의 키를 가짐
3. 모든 리프 노드는 같은 레벨에 위치
4. 노드 내의 키들은 정렬되어 있음

시각적 표현

3차 B-Tree (m=3):
       [10, 20]
      /    |    \
   [5]   [15]   [25, 30]
  /  \   /  \   /   |   \
[1]  [7] [12] [17] [23] [27] [35]

활용

• 데이터베이스 인덱스: MySQL, PostgreSQL
• 파일 시스템: B+ Tree 변형 사용
• 대용량 데이터 검색: 디스크 I/O 최소화

기본 연산

class BTreeNode:
    def __init__(self, degree):
        self.degree = degree
        self.keys = []
        self.children = []
        self.is_leaf = True
    
    def search(self, key):
        """키 검색"""
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        
        if i < len(self.keys) and key == self.keys[i]:
            return True
        
        if self.is_leaf:
            return False
        
        return self.children[i].search(key)

---

7. 트라이 (Trie)

개념

• 정의: 문자열을 저장하고 검색하기 위한 트리 자료구조
• 다른 이름: Prefix Tree, Digital Tree
• 특징: 공통 접두사를 공유하는 문자열들을 효율적으로 저장

구조와 특성

• 루트: 빈 문자열을 나타냄
• 경로: 루트에서 노드까지의 경로가 문자열을 형성
• 종료 표시: 문자열의 끝을 나타내는 플래그

시각적 표현

문자열: "CAR", "CARD", "CAT", "DOG"

        Root
       /    \
      C      D
      |      |
      A      O
      |      |
      R      G
     /|\     |
    $ T D    $
      | |
      $ $

$ = 문자열 끝 표시

장점과 단점

장점:

• 문자열 검색: O(문자열 길이)
• 접두사 검색에 효율적
• 자동완성 기능 구현 용이

단점:

• 메모리 사용량이 많음
• 구현이 복잡함

활용 사례

• 자동완성: 검색엔진, IDE
• 사전: 단어 검색 시스템
• IP 라우팅: 네트워크 라우팅 테이블
• 문자열 매칭: 패턴 검색

Python 구현

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """단어 삽입"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word):
        """단어 검색"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word
    
    def starts_with(self, prefix):
        """접두사로 시작하는 단어 존재 확인"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def get_words_with_prefix(self, prefix):
        """접두사로 시작하는 모든 단어 반환"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        words = []
        self._collect_words(node, prefix, words)
        return words
    
    def _collect_words(self, node, current_word, words):
        """DFS로 모든 단어 수집"""
        if node.is_end_of_word:
            words.append(current_word)
        
        for char, child_node in node.children.items():
            self._collect_words(child_node, current_word + char, words)

---

8. 최단 경로 알고리즘

다익스트라 알고리즘 (Dijkstra's Algorithm)

개념

• 목적: 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로
• 제약: 음수 가중치가 없는 그래프
• 시간 복잡도: O((V + E) log V) - 우선순위 큐 사용

동작 원리

1. 시작 정점의 거리를 0으로, 나머지는 무한대로 초기화
2. 방문하지 않은 정점 중 거리가 가장 짧은 정점 선택
3. 해당 정점의 인접 정점들의 거리 갱신
4. 모든 정점을 방문할 때까지 반복

시각적 예시

그래프:
A ──2── B ──3── C
│       │       │
1       4       2
│       │       │
D ──5── E ──1── F

다익스트라 실행 (시작: A):
단계 1: A(0) 선택 → B(2), D(1) 갱신
단계 2: D(1) 선택 → E(6) 갱신
단계 3: B(2) 선택 → C(5), E(6) 확인
단계 4: C(5) 선택 → F(7) 갱신
...

Python 구현

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    distances = defaultdict(lambda: float('inf'))
    distances[start] = 0
    previous = {}
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current
                heapq.heappush(pq, (distance, neighbor))
    
    return distances, previous

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

개념

• 목적: 모든 정점 쌍 간의 최단 경로
• 특징: 음수 가중치 허용 (음수 사이클 없는 경우)
• 시간 복잡도: O(V³)

동작 원리

• 경유점 k를 거쳐서 i에서 j로 가는 경로와 직접 가는 경로 비교
• distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

Python 구현

def floyd_warshall(graph):
    vertices = list(graph.keys())
    n = len(vertices)
    
    # 거리 행렬 초기화
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 자기 자신까지의 거리는 0
    for i in range(n):
        dist[i][i] = 0
    
    # 직접 연결된 간선들의 가중치 설정
    for i, vertex_i in enumerate(vertices):
        for neighbor, weight in graph[vertex_i]:
            j = vertices.index(neighbor)
            dist[i][j] = weight
    
    # 플로이드-워셜 알고리즘
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

---

9. 최소 신장 트리

개념

• 신장 트리: 그래프의 모든 정점을 포함하는 트리
• 최소 신장 트리 (MST): 가중치의 합이 최소인 신장 트리
• 특성: n개 정점, n-1개 간선, 사이클 없음

활용 사례

• 네트워크 설계: 최소 비용으로 모든 지점 연결
• 클러스터링: 데이터 군집화
• 회로 설계: 최소 비용 연결

크루스칼 알고리즘 (Kruskal's Algorithm)

개념

• 아이디어: 간선을 가중치 순으로 정렬하여 사이클을 만들지 않는 간선만 선택
• 시간 복잡도: O(E log E)
• 자료구조: Union-Find (분리 집합)

동작 과정

그래프:
A ──1── B ──4── C
│       │       │
2       3       5
│       │       │
D ──6── E ──7── F

1. 간선 정렬: (A,B,1), (A,D,2), (B,E,3), (B,C,4), (C,F,5), (D,E,6), (E,F,7)
2. 간선 선택: (A,B), (A,D), (B,E), (B,C), (C,F)
3. MST 완성: 총 가중치 = 15

Python 구현

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # 가중치로 정렬
    uf = UnionFind(n)
    mst = []
    total_weight = 0
    
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_weight += weight
    
    return mst, total_weight

프림 알고리즘 (Prim's Algorithm)

개념

• 아이디어: 시작 정점에서 시작하여 트리를 점진적으로 확장
• 시간 복잡도: O(V²) 또는 O((V + E) log V) - 우선순위 큐 사용

동작 과정

1. 임의의 정점에서 시작
2. 현재 트리와 연결된 간선 중 가중치가 최소인 간선 선택
3. 새로운 정점을 트리에 추가
4. 모든 정점이 포함될 때까지 반복

Python 구현

def prim(graph, start):
    mst = []
    visited = {start}
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    
    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        
        if v in visited:
            continue
        
        visited.add(v)
        mst.append((u, v, weight))
        
        for neighbor, weight in graph[v]:
            if neighbor not in visited:
                heapq.heappush(edges, (weight, v, neighbor))
    
    return mst

---

정리

알고리즘 선택 가이드

문제 유형	추천 알고리즘	시간 복잡도
그래프 탐색	BFS/DFS	O(V + E)
최단 경로 (단일 출발점)	다익스트라	O((V + E) log V)
최단 경로 (모든 쌍)	플로이드-워셜	O(V³)
최소 신장 트리	크루스칼/프림	O(E log E)
의존성 순서	위상 정렬	O(V + E)
문자열 검색	트라이	O(문자열 길이)

그래프 표현 방식 선택

그래프 특성	추천 표현 방식	이유
조밀한 그래프	인접 행렬	간선 확인이 빠름
희소한 그래프	인접 리스트	메모리 효율적
가중치 그래프	인접 리스트	가중치 저장 용이
자주 변경되는 그래프	인접 리스트	동적 변경 용이