기쁘달

그래프 (Graph)

8 min read

개념

노드(정점)와 간선으로 이루어진 자료구조

객체 간의 관계를 표현하는 비선형 구조

그래프 용어

    1 --- 2
    |     |
    3 --- 4 --- 5
  • 정점(Vertex, Node): 노드 (1, 2, 3, 4, 5)
  • 간선(Edge): 정점을 연결하는 선
  • 차수(Degree): 정점에 연결된 간선의 수
  • 경로(Path): 정점에서 다른 정점으로 가는 길
  • 사이클(Cycle): 시작과 끝이 같은 경로

그래프의 종류

1. 무방향 그래프 (Undirected Graph)

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

간선에 방향이 없음 (양방향)

2. 방향 그래프 (Directed Graph)

1 → 2
↓   ↓
3 → 4

간선에 방향이 있음

3. 가중치 그래프 (Weighted Graph)

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

간선에 가중치(비용)가 있음

4. 완전 그래프 (Complete Graph)

1 --- 2
|\ /|
| X |
|/ \|
3 --- 4

모든 정점이 서로 연결됨

5. 연결 그래프 vs 비연결 그래프

연결 그래프:         비연결 그래프:
1 --- 2             1 --- 2    5
|     |             |     |    |
3 --- 4             3 --- 4    6

6. 순환 그래프 vs 비순환 그래프

순환 그래프:         비순환 그래프 (트리):
1 --- 2                 1
|     |                / \
3 --- 4               2   3
                     /
                    4

그래프 표현 방법

1. 인접 행렬 (Adjacency Matrix)

2차원 배열로 표현

# 그래프:
#   0 --- 1
#   |     |
#   2 --- 3
 
# 무방향 그래프
graph = [
    [0, 1, 1, 0],  # 0번 정점
    [1, 0, 0, 1],  # 1번 정점
    [1, 0, 0, 1],  # 2번 정점
    [0, 1, 1, 0]   # 3번 정점
]
 
# 연결 확인: O(1)
print(graph[0][1])  # 1 (연결됨)
 
# 모든 인접 정점 확인: O(V)
for i in range(len(graph[0])):
    if graph[0][i]:
        print(f"0과 {i} 연결")

장점:

  • 두 정점 간 연결 확인 O(1)
  • 구현 간단

단점:

  • 공간복잡도 O(V²) - 메모리 낭비
  • 모든 인접 정점 찾기 O(V)

2. 인접 리스트 (Adjacency List)

리스트의 배열로 표현

# 그래프:
#   0 --- 1
#   |     |
#   2 --- 3
 
# 무방향 그래프
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
 
# 또는 리스트로
graph = [
    [1, 2],     # 0번 정점
    [0, 3],     # 1번 정점
    [0, 3],     # 2번 정점
    [1, 2]      # 3번 정점
]
 
# 모든 인접 정점 확인: O(degree)
for neighbor in graph[0]:
    print(f"0과 {neighbor} 연결")

장점:

  • 공간복잡도 O(V + E) - 효율적
  • 모든 인접 정점 찾기 빠름

단점:

  • 두 정점 간 연결 확인 O(degree)

3. 간선 리스트 (Edge List)

모든 간선을 리스트로 저장

# 그래프:
#   0 --- 1
#   |     |
#   2 --- 3
 
# 무방향 그래프
edges = [
    (0, 1),
    (0, 2),
    (1, 3),
    (2, 3)
]
 
# 가중치 그래프
weighted_edges = [
    (0, 1, 5),  # (시작, 끝, 가중치)
    (0, 2, 3),
    (1, 3, 2),
    (2, 3, 1)
]

활용: 크루스칼 알고리즘, Union-Find

Python 구현

그래프 클래스 (인접 리스트)

from collections import defaultdict
 
class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
 
    def add_edge(self, u, v, weight=1):
        """간선 추가"""
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v].append((u, weight))
 
    def get_neighbors(self, v):
        """인접 정점 반환"""
        return self.graph[v]
 
    def print_graph(self):
        """그래프 출력"""
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")
 
# 사용 예시
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.print_graph()
# 0: [(1, 1), (2, 1)]
# 1: [(0, 1), (3, 1)]
# 2: [(0, 1), (3, 1)]
# 3: [(1, 1), (2, 1)]

그래프 입력 처리

1. 간선 리스트로 입력

# 입력 형식:
# 4 5          (정점 수, 간선 수)
# 0 1
# 0 2
# 1 3
# 2 3
# 1 2
 
n, m = map(int, input().split())  # 정점 수, 간선 수
graph = [[] for _ in range(n)]
 
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)  # 무방향 그래프

2. 가중치 그래프 입력

# 입력 형식:
# 4 5
# 0 1 5        (시작, 끝, 가중치)
# 0 2 3
# 1 3 2
# 2 3 1
# 1 2 4
 
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
 
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))  # 무방향

3. 인접 행렬로 입력

# 입력 형식:
# 4
# 0 1 1 0
# 1 0 0 1
# 1 0 0 1
# 0 1 1 0
 
n = int(input())
graph = []
 
for _ in range(n):
    row = list(map(int, input().split()))
    graph.append(row)

그래프 기본 연산

1. 정점 개수, 간선 개수

def count_vertices(graph):
    return len(graph)
 
def count_edges(graph):
    """무방향 그래프의 간선 수"""
    count = sum(len(neighbors) for neighbors in graph.values())
    return count // 2  # 양방향이므로 나누기 2

2. 차수 계산

def degree(graph, v):
    """정점 v의 차수"""
    return len(graph[v])
 
def in_degree(graph, v):
    """방향 그래프에서 진입 차수"""
    count = 0
    for vertex in graph:
        for neighbor, _ in graph[vertex]:
            if neighbor == v:
                count += 1
    return count

3. 경로 존재 확인

def has_path(graph, start, end, visited=None):
    """start에서 end로 가는 경로가 있는지 확인"""
    if visited is None:
        visited = set()
 
    if start == end:
        return True
 
    visited.add(start)
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            if has_path(graph, neighbor, end, visited):
                return True
 
    return False

그래프 vs 트리

특성그래프트리
정의정점과 간선계층적 그래프
사이클가능불가능
루트없음있음
간선 수제한 없음V - 1개
연결비연결 가능항상 연결

트리는 사이클이 없는 연결 그래프

추천 연습 문제

기초

중급

핵심 요약

개념설명
표현 방법인접 행렬, 인접 리스트
인접 행렬공간 O(V²), 연결 확인 O(1)
인접 리스트공간 O(V+E), 탐색 효율적
탐색DFS, BFS로 순회

표현 방법 선택 가이드

인접 행렬 사용 시

  • 정점 수가 적을 때 (V ≤ 1000)
  • 간선이 많을 때 (밀집 그래프)
  • 두 정점 간 연결 확인이 빈번할 때

인접 리스트 사용 시

  • 정점 수가 많을 때
  • 간선이 적을 때 (희소 그래프)
  • 모든 인접 정점 탐색이 필요할 때
  • 대부분의 경우 추천

그래프 뷰

백링크