Blog
Series
Projects
블로그로 돌아가기
자료구조크래프톤 정글

[자료구조] 그래프

약 9분 소요
[자료구조] 그래프

🎉 드디어 Week02까지 무사히 마치고 Week 03의 첫 번째 관문, 그래프(Graph)에 도달했다! 🥳

아마 많은 사람들이 '그래프'라는 단어를 들으면 수학 시간의 꺾은선그래프를 떠올릴지도 모른다👀

하지만 자료구조의 세계에서 그래프는 그보다 훨씬 더 다채롭고 강력한 개념이다.

이번 주부터 우리는 이 그래프의 세계를 탐험하며 DFS, BFS, 그리고 위상정렬까지 나아갈 예정이다.

그 첫걸음으로, 오늘은 그래프가 무엇인지, 어떻게 생겼고, 왜 중요한지에 대해 알아보자!

그래프란 ? 👬

💡 "점과 이 점들을 잇는 선의 모음"

자료구조에서 말하는 그래프는 아주 간단하게 이렇게 정의할 수 있다.

이를 아래의 예시를 통해 보다 직관적으로 이해해 보도록 하자

social-network페이스북 혹은 인스타그램을 하다보면 **“알 수도 있는 사람”**을 추천해주는 경우가 있다.

대체 한 번도 만난 적 없는 내 친구의 친구를 어떻게 알고 추천해 주는 걸까?

이 서비스의 뒤편에 바로 **그래프(Graph)**가 있다.

위의 그림은 두 가지로 이루어져 있다.

  • 하나하나의 사용자(점)

  • 사용자들을 잇는 친구라는 관계(선)

페이스북이 ‘A라는 사람을 알 수도 있습니다’라고 추천하는 것은,

나 → 내 친구 → 친구의 친구 A로 이어지는 경로를 발견했기 때문이다.

이처럼 그래프는 우리 눈에 보이지 않는 '관계'를 시각적으로 표현하고,

그 관계 속에서 새로운 정보나 의미를 찾아내는 아주 강력한 도구인 것이다.

그래프의 구조와 표현법 🛠️

  • 정점 (Vertex 또는 Node) 그래프의 가장 기본 단위로, 데이터를 가진 객체를 의미한다.

    • 소셜 네트워크에서는 사용자 한 명 한 명이 정점이 된다.

    • **Vertex**와 **Node**는 같은 의미로 사용되므로 혼동할 필요 없다.

  • 간선 (Edge 또는 Arc) 정점 간의 관계를 나타내는 선이다. 여기서 방향성에 따라 용어를 구분해볼 수 있다.

    • Edge: 주로 무방향 그래프(Undirected Graph)에서 양방향 관계를 나타낼 때 사용한다.

      • 두 사용자 간의 페이스북 친구 관계가 좋은 예다.

      • A와 B가 친구라면, 이는 양방향으로 성립한다.

    • Arc: 주로 방향 그래프(Directed Graph)에서 단방향 관계를 나타낼 때 사용한다.

      • 인스타그램 팔로우 관계를 생각하면 쉽다.

      • A가 B를 팔로우하더라도, B가 A를 팔로우하는 것은 아니기 때문

    하지만 이 둘 역시 종종 혼용되기도 하니, '간선에 방향성이 있나 없나'라는 핵심적인 차이만 기억해두자!

  • 가중치 (Weight)

    • 간선에 부여되는 숫자 값으로, 정점과 정점을 잇는 길이 얼마나 ‘중요한지’ 또는 ‘비용이 많이 드는지’를 나타낸다.

    • 모든 연결이 다 똑같은 가치를 갖지는 않는 현실 세계의 문제를 표현하기 위해 사용

  • 인접 (Adjacent)

    • 두 정점이 간선으로 직접 연결되어 있으면 인접해있다고 한다.

  • 차수 (Degree)

    • (무방향 그래프에서) 하나의 정점에 연결된 간선(Edge)의 수. (페이스북에선 인싸일수록 차수가 높겠지)

  • 진입/진출 차수 (In-degree/Out-degree)

    • (방향 그래프에서) 한 정점으로 '들어오는' 간선(Arc)의 수와, 그 정점에서 '나가는' 간선의 수를 따로 센다.

    • 인스타그램에서 나의 팔로워 수는 진입 차수, 나의 팔로잉 수는 진출 차수라 볼 수 있다.

  • 경로 (Path): 한 정점에서 다른 정점으로 간선을 따라 이동할 때 거치는 정점들의 순서

그래프의 종류 🗂️

모든 그래프가 똑같이 생기지는 않기 때문에, 문제의 상황에 따라 우리는 각기 다른 특징을 가진 그래프를 사용해야 한다.

1. 방향 그래프 vs 무방향 그래프 (Directed vs Undirected)

그래프의 간선에 방향성이 존재하는지를 기준으로 나눈 구분

⇒ 관계의 종류(단방향 vs 양방향)를 모델링하는 데 중요!

directed-vs-undirected

  • 무방향 그래프 간선(Edge)에 방향이 없는 그래프

    • 페이스북 친구 관계가 대표적이다.

    • A와 B가 연결되어 있다면 B와 A도 연결된, 양방향 관계이며, 이는 A-B라는 하나의 간선으로 표현된다.

  • 방향 그래프 간선(Arc)에 방향이 있는 그래프

    • 인스타그램 팔로우 관계가 여기에 해당한다.

    • A가 B를 팔로우(A→B)했다고 해서 B가 A를 팔로우(B→A)하는 것은 아닌, 단방향 관계를 표현할 때 사용한다.

2. 비가중치 그래프 vs 가중치 그래프 (Unweighted vs Weighted)

그래프의 각 간선에 가중치(비용, 거리 등) 부여 여부를 기준으로 나눈 구분

  • 비가중치 그래프 모든 간선의 가치가 동일하다고 가정하는 그래프

    • 단순히 친구 관계의 연결 여부에만 관심이 있다면 비가중치 그래프로 모델링할 수 있다.

  • 가중치 그래프 각 간선에 가중치(비용, 거리, 시간 등)를 부여한 그래프

    • 네비게이션에서 도로마다 다른 '거리(km)'나 '소요시간'을 표시하는 것이 대표적인 예

    • 최단 경로 문제가 대부분 가중치 그래프에서 다뤄진다.

    • 사용자 간의 '친밀도'를 메시지 교환 횟수 등으로 계산하여 간선에 가중치로 부여하면, '더 가까운 친구'를 찾는 등의 분석이 가능해진다.

3. 희소 그래프 vs 밀집 그래프 (Sparse vs Dense)

그래프의 간선이 얼마나 빽빽하게 연결되어 있는지를 기준으로 나눈 구분

⇒ 어떤 방식으로 그래프를 구현할 지 결정하는데(인접 행렬 vs 인접 리스트) 중요!

  • 희소 그래프 정점의 개수 $V$에 비해 간선의 개수 $E$가 매우 적은 그래프 (E≪V^2)

    • 간선의 개수가 대략 정점 개수에 비례 (E≈V)

    • 희소 그래프의 대표적인 예시는 트리( E=V-1 )

    • 대부분의 알고리즘 문제나 실제로 마주하는 서비스는 희소 그래프에 해당

  • 밀집 그래프 정점의 개수에 비해 간선의 개수가 매우 많은 그래프(E≈V^2)

    • 정점 대부분이 서로 연결되어 있다.

그래프 구현하기: 인접 행렬 vs 인접 리스트 👨🏻‍💻

자, 이제 이론을 넘어서 실제 코드로 그래프를 직접 만들어볼 시간이다.

그래프를 코드로 표현하는 데는 크게 **인접 행렬(Adjacency Matrix)**과 인접 리스트(Adjacency List),

두 가지 방법이 있다.

1. 인접 행렬 (Adjacency Matrix)

$V$개의 정점을 가지는 그래프를 V*V 크기의 2차원 배열로 표현하는 방식이다.

matrix[i][j]의 값이 1이면 정점 i와 j가 연결되어 있다는 뜻이다.

(⇒ 가중치 그래프라면 1대신 가중치 값을 넣는다.)

  • 2차원 리스트로 구현

    빠른 구현이 중요할 때는 2차원 리스트를 선언해서 직관적으로 바로 구현이 가능하다.

    # 4개의 정점(0, 1, 2, 3)을 가진 그래프를 가정
# 인접 행렬을 Python의 2차원 리스트로 바로 구현
adj_matrix = [
    [0, 1, 1, 0],  # 0번 정점은 1, 2번과 연결
    [1, 0, 0, 1],  # 1번 정점은 0, 3번과 연결
    [1, 0, 0, 1],  # 2번 정점은 0, 3번과 연결
    [0, 1, 1, 0]   # 3번 정점은 1, 2번과 연결
]

# 0번과 2번 정점이 연결되어 있는지 O(1) 시간 복잡도로 즉시 확인 가능
if adj_matrix[0][2] == 1:
    print("0번과 2번은 연결되어 있다!")

  • 클래스로 구조화하여 구현

    그래프라는 '개념'과 그 '행동'(간선 추가, 삭제 등)을 하나의 캡슐로 묶어 클래스로 구현하면, 코드의 구조를 이해하고 확장하기에 훨씬 용이하다. 따라서 클래스로도 한번 구현해보도록 하자!

    class GraphMatrix:
    def __init__(self, num_vertices):
        self.V = num_vertices
        self.adj_matrix = [[0] * self.V for _ in range(self.V)]

    def add_edge(self, u, v):
        # 무방향 그래프이므로 양쪽 모두 1로 설정
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1

    def __str__(self): # print() 함수로 그래프 상태를 쉽게 확인하기 위함
        return "\n".join([" ".join(map(str, row)) for row in self.adj_matrix])

# 4개의 정점을 가진 그래프 객체 생성
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print(g)
# 0 1 1 0
# 1 0 0 1
# 1 0 0 1
# 0 1 1 0

    인접 행렬 방식 장/단점

    • 장점: 두 정점의 연결 여부를 O(1) 만에 즉시 확인할 수 있다.

    • 단점: 정점의 개수가 많고 간선이 적은 희소 그래프(Sparse Graph)의 경우, O(V^2)의 공간 복잡도 때문에 메모리 낭비가 심하다.

2. 인접 리스트 (Adjacency List)

인접 리스트는 각 정점마다, 해당 정점과 연결된 이웃 정점들의 목록을 리스트나 딕셔너리로 저장하는 방식이다.

  • 딕셔너리/리스트로 구현

    인접 리스트의 핵심은 "각 정점에 연결된 리스트"이므로, 이를 딕셔너리나 리스트의 리스트로 바로 구현하는 것이 가장 빠르고 일반적이다.

    from collections import defaultdict

# 인접 리스트를 Python의 딕셔너리로 바로 구현
# defaultdict를 사용하면 키가 없을 때 자동으로 빈 리스트를 생성해줘서 편리하다.
adj_list = defaultdict(list)
adj_list[0] = [1, 2]
adj_list[1] = [0, 3]
adj_list[2] = [0, 3]
adj_list[3] = [1, 2]

# 1번 정점과 연결된 모든 정점들을 효율적으로 순회 가능
for neighbor in adj_list[1]:
    print(f"1번의 이웃: {neighbor}")
#    1번의 이웃: 0
#    1번의 이웃: 3

  • 클래스로 구조화하여 구현

    마찬가지로 인접 리스트 방식도 클래스로 캡슐화하면 그래프라는 객체의 책임과 역할이 명확해진다.

    from collections import defaultdict

class GraphList:
    def __init__(self):
        self.adj_list = defaultdict(list)

    def add_edge(self, u, v):
        # 무방향 그래프이므로 양쪽 모두의 리스트에 추가
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def __str__(self):
        return "\n".join([f"{vertex}: {neighbors}" for vertex, neighbors in self.adj_list.items()])

# 그래프 객체 생성
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print(g)
# 0: [1, 2]
# 1: [0, 3]
# 2: [0, 3]
# 3: [1, 2]

    인접 리스트 방식 장/단점

    • 장점: 실제로 존재하는 간선 정보만 저장하므로 O(V+E)의 공간 복잡도를 가진다. ⇒ 희소 그래프에 절대적으로 유리하다.

    • 단점: 두 정점의 연결 여부를 확인하려면 한 정점의 리스트를 모두 탐색해야 하므로, 인접 행렬보다 시간이 더 걸릴 수 있다(최악의 경우 O(V)).

  • 장점: 실제로 존재하는 간선의 정보만 저장하므로, O(V+E)의 공간 복잡도를 가진다. 희소 그래프(Sparse Graph)에 절대적으로 유리하여 메모리 효율이 뛰어나다.

  • 단점: 두 정점의 연결 여부를 확인하려면 한 정점의 리스트를 모두 탐색해야 하므로, 인접 행렬보다 시간이 더 걸릴 수 있다(최악의 경우 O(V)).


👨🏻‍💻그래서 뭐 씀?

코딩 테스트나 실제 애플리케이션에서 마주하는 그래프는 대부분 희소 그래프다.

따라서 별다른 조건이 없다면 인접 리스트 방식을 기본으로 채택하는 것이

메모리와 성능 면에서 현명한 선택으로 보인다!


실제 그래프 사용 사례 🌐

실제로 그래프는 어디서 사용되고 있을까?

  1. 소셜 네트워크 서비스 (SNS): 사용자 노드를 연결해 친구 관계를 분석하고, 추천이나 영향력 있는 사용자 탐색에 활용

  2. 네비게이션 및 지도 앱 도시/교차로를 정점, 도로를 간선, 거리/시간을 가중치로 하여 최단 경로를 계산

  3. 유튜브 쇼츠 & 인스타그램 릴스 추천 알고리즘 '나'만의 데이터가 아닌 '우리'의 데이터를 활용해, 숨겨진 취향의 연결고리를 찾아내는 그래프 활용의 정수

    • 사용자, 영상, 채널, 사운드를 각각의 '정점'으로 보고, 이들의 상호작용(시청, 좋아요, 공유)을 '간선'으로 연결

    • 단순히 '고양이 영상'을 봤다고 비슷한 영상을 보여주는 것을 넘어, 나와 취향이 비슷한 사람들의 네트워크를 분석

    • 내가 시청한 영상을 좋아한 다른 사용자들이 소비한, 전혀 예상치 못한 콘텐츠를 추천의 후보로 가져옴

    • 이때, 시청 시간이나 '좋아요' 여부를 '가중치'로 두어 관계의 깊이를 측정하고 추천의 정밀도를 높임

알고리즘 문제에서는 어떻게 나올까? 🧩

그래프는 알고리즘 문제의 단골 주제다. 앞으로 자세히 다룰 내용이지만, 여기서는 어떤 유형들이 있는지 맛보기로 알아보자.

  1. 그래프 탐색 (DFS/BFS)

    • "한 지점에서 다른 지점까지 갈 수 있는가?" 또는 "연결된 덩어리가 총 몇 개인가?"와 같은 문제를 푸는 데 사용

    • DFS는 스택이나 재귀를 이용해 한 길을 깊게 파고드는 방식이고, BFS는 큐를 이용해 현재 지점에서 가까운 곳부터 넓게 탐색하는 방식

  2. 최단 경로 (Shortest Path)

    • A에서 B까지 가는 가장 빠르거나 저렴한 경로는 무엇인가?"를 찾는 문제

    • 가중치 그래프에서 주로 사용되며, 다익스트라(Dijkstra) 알고리즘이 가장 유명

      • 다익스트라는 우선순위 큐를 사용하여, 출발점으로부터 가장 가까운 정점을 계속해서 선택해 나가는 탐욕적인(Greedy) 접근 방식을 취함

  3. 위상 정렬 (Topological Sort)

    • "선후 관계가 있는 작업들을 어떤 순서로 처리해야 하는가?"를 해결

    • 사이클이 없는 방향 그래프에서만 정의되며, 진입 차수(In-degree)를 활용하는 것이 핵심

    • 진입 차수가 0인 정점(선행 작업이 없는 정점)부터 큐에 넣고 처리하며, 연결된 정점들의 진입 차수를 갱신하는 과정을 반복

결론 ✨

"관계를 표현하는 곳에 그래프가 있다."

여기까지 관계를 모델링하는 강력한 도구, 그래프에 대해 알아보았다.

이번 week3에 배울 DFS, BFS, 위상 정렬은 모두 오늘 다진 기초 위에 세워지는 기둥과 같다.

다음엔 그래프를 사용하는 강력한 알고리즘 기법인 DFS에 대해 알아보자!