그래프 (Graph)

그래프(Graph)는 정점(Vertex)과 간선(Edge)의 집합으로 대상 사이의 연결 관계를 표현하는 비선형 자료구조다. 소셜 네트워크의 친구 관계, 도시를 잇는 도로망, 웹 페이지 사이의 링크처럼 개체가 서로 얽혀 있는 문제를 모델링할 때 그래프를 사용한다. 그래프는 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 구현하며, 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)으로 순회한다.

그래프의 기본 개념과 용어

그래프는 수학적으로 G = (V, E)로 표기한다. V는 정점의 집합이고 E는 두 정점을 잇는 간선의 집합이다. 트리(Tree)가 부모와 자식이라는 계층 관계를 강제하는 반면, 그래프는 어떤 정점이든 서로 연결될 수 있고 사이클(Cycle)도 허용한다. 사실 트리는 사이클이 없고 모든 정점이 연결된 그래프의 특수한 형태다.

면접에서 자주 등장하는 용어를 정리하면 다음과 같다.

• 차수(Degree): 한 정점에 연결된 간선의 수다. 방향 그래프에서는 들어오는 간선을 세는 진입 차수(In-degree)와 나가는 간선을 세는 진출 차수(Out-degree)로 나눈다.
• 경로(Path): 간선을 따라 한 정점에서 다른 정점으로 이동하는 정점의 나열이다.
• 사이클(Cycle): 시작 정점으로 다시 돌아오는 경로다. 사이클이 없는 방향 그래프를 DAG(Directed Acyclic Graph)라 부르며 작업 순서 결정, 즉 위상 정렬(Topological Sort)의 대상이 된다.
• 연결 그래프(Connected Graph): 임의의 두 정점 사이에 항상 경로가 존재하는 그래프다.

방향, 무방향, 가중치에 따른 분류

무방향 그래프(Undirected Graph)는 간선에 방향이 없어 (A, B) 간선이 있으면 A에서 B로도, B에서 A로도 이동할 수 있다. 친구 관계처럼 상호적인 관계를 표현한다. 방향 그래프(Directed Graph)는 간선 <A, B>가 A에서 B로 가는 한 방향만 의미한다. 팔로우 관계나 작업의 선후 관계가 대표적인 예다.

가중치 그래프(Weighted Graph)는 간선마다 비용이나 거리 같은 값을 부여한 그래프다. 도시 사이의 거리, 네트워크 전송 비용을 표현할 때 쓰며, 다익스트라(Dijkstra) 최단 경로 알고리즘이나 최소 신장 트리(Minimum Spanning Tree)를 구하는 크루스칼(Kruskal), 프림(Prim) 알고리즘이 가중치 그래프 위에서 동작한다.

인접 행렬과 인접 리스트

인접 행렬은 정점 수 V에 대해 V x V 크기의 2차원 배열을 만들고, 정점 i에서 j로 가는 간선이 있으면 matrix[i][j]에 1 또는 가중치를 저장하는 방식이다. 두 정점의 연결 여부를 O(1)에 확인할 수 있지만, 간선 유무와 무관하게 항상 O(V^2)의 공간을 차지한다.

인접 리스트는 정점마다 연결된 이웃 정점의 목록을 저장하는 방식이다. 공간을 O(V + E)만 사용하므로 실제 그래프처럼 간선이 드문 희소 그래프(Sparse Graph)에 유리하다. 다만 특정 간선의 존재 여부를 확인하려면 해당 정점의 리스트를 따라가야 하므로 최악에 O(V)가 걸린다.

연산	인접 행렬	인접 리스트
공간	O(V^2)	O(V + E)
간선 (i, j) 존재 확인	O(1)	O(차수), 최악 O(V)
정점 i의 모든 이웃 순회	O(V)	O(차수)
간선 추가	O(1)	O(1)
유리한 경우	밀집 그래프, 간선 조회가 잦을 때	희소 그래프, 순회가 잦을 때

파이썬(Python)으로 두 방식을 표현하면 다음과 같다.

# 정점 4개, 간선: 0-1, 0-2, 1-3 (무방향)

# 인접 행렬
matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0],
]

# 인접 리스트
adj = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
}

from collections import deque

def bfs(adj, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for nxt in adj[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)

def dfs(adj, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for nxt in adj[node]:
        if nxt not in visited:
            dfs(adj, nxt, visited)