그래프 기초와 표현 완벽 가이드

그래프 자료구조의 기본 개념부터 인접 행렬, 인접 리스트까지 초급 개발자를 위해 쉽게 설명합니다. 실무에서 활용되는 네트워크 분석의 기초를 다집니다.

---

목차

1. 그래프란_무엇인가
2. 정점과_간선
3. 그래프_이론과_네트워크_분석
4. 인접_행렬과_인접_리스트
5. 그래프의_구조와_종류
6. 자아_중심_네트워크
7. 그래프_표현_방식_선택

---

1. 그래프란 무엇인가

어느 날 김개발 씨는 SNS 친구 추천 기능을 구현하라는 과제를 받았습니다. "친구의 친구를 어떻게 찾아내지?" 고민하던 그에게 박시니어 씨가 다가왔습니다.

"그래프 자료구조를 알면 쉽게 해결할 수 있어요."

그래프는 한마디로 점과 선으로 이루어진 관계의 지도입니다. 마치 지하철 노선도처럼 역(점)과 노선(선)이 연결된 구조라고 생각하면 됩니다.

이것을 제대로 이해하면 복잡한 관계 데이터를 효율적으로 다룰 수 있습니다.

다음 코드를 살펴봅시다.

# 가장 기본적인 그래프 표현
# 딕셔너리를 사용해 관계를 표현합니다
graph = {
    'A': ['B', 'C'],      # A는 B, C와 연결
    'B': ['A', 'D', 'E'], # B는 A, D, E와 연결
    'C': ['A', 'F'],      # C는 A, F와 연결
    'D': ['B'],           # D는 B와 연결
    'E': ['B', 'F'],      # E는 B, F와 연결
    'F': ['C', 'E']       # F는 C, E와 연결
}

# A와 연결된 모든 노드 확인
print(f"A의 이웃: {graph['A']}")  # 출력: A의 이웃: ['B', 'C']

김개발 씨는 입사한 지 얼마 되지 않은 주니어 개발자입니다. 오늘 팀장님께서 흥미로운 과제를 주셨습니다.

"우리 서비스에 친구 추천 기능을 넣어봐요. 친구의 친구를 추천해주는 거예요." 처음에 김개발 씨는 데이터베이스 테이블만으로 해결하려고 했습니다.

하지만 친구 관계가 복잡해질수록 쿼리는 점점 복잡해졌고, 성능은 눈에 띄게 느려졌습니다. 그때 박시니어 씨가 화이트보드에 동그라미 몇 개를 그리고 선으로 연결했습니다.

"이게 바로 그래프예요. 프로그래밍에서 관계를 표현하는 가장 기본적인 방법이죠." 그렇다면 그래프란 정확히 무엇일까요?

쉽게 비유하자면, 그래프는 마치 지하철 노선도와 같습니다. 각 역은 하나의 점이 되고, 역과 역을 잇는 노선은 선이 됩니다.

서울역에서 시청역으로 갈 수 있듯이, 그래프에서도 한 점에서 다른 점으로 이동할 수 있습니다. 수학에서 말하는 그래프와는 조금 다릅니다.

x축과 y축으로 이루어진 좌표 그래프가 아니라, 정점과 간선으로 이루어진 관계도를 의미합니다. 이것이 바로 컴퓨터 과학에서 말하는 그래프입니다.

그래프가 없던 시절에는 어땠을까요? 개발자들은 복잡한 관계 데이터를 배열이나 테이블로 억지로 표현해야 했습니다.

A가 B와 친구이고, B가 C와 친구라는 사실을 추적하려면 여러 테이블을 조인해야 했습니다. 그래프를 사용하면 이런 관계를 직관적으로 표현할 수 있습니다.

위의 코드에서 딕셔너리 하나로 6개의 점과 그 연결 관계를 깔끔하게 나타냈습니다. 실제 현업에서 그래프는 정말 다양한 곳에 활용됩니다.

소셜 네트워크의 친구 관계, 도로망의 교차로와 도로, 컴퓨터 네트워크의 라우터 연결, 심지어 웹페이지 간의 하이퍼링크까지 모두 그래프로 표현할 수 있습니다. 박시니어 씨의 설명을 들은 김개발 씨는 고개를 끄덕였습니다.

"아, 그러니까 복잡한 관계도 점과 선으로 단순화하면 되는 거군요!"

실전 팁

💡 - 그래프는 관계를 표현하는 자료구조로, 좌표 그래프와 다릅니다

• 파이썬에서는 딕셔너리로 그래프를 간단히 표현할 수 있습니다

---

2. 정점과 간선

"그래프가 점과 선으로 이루어져 있다는 건 알겠는데, 정확한 용어가 뭐예요?" 김개발 씨가 물었습니다. 박시니어 씨는 미소를 지으며 대답했습니다.

"그래프의 기본 구성 요소, 정점과 간선에 대해 알아볼까요?"

**정점(Vertex)**은 그래프에서 데이터를 담는 점입니다. **노드(Node)**라고도 부릅니다.

**간선(Edge)**은 정점들을 연결하는 선으로, 관계나 연결을 나타냅니다. 이 두 요소가 그래프의 전부입니다.

다음 코드를 살펴봅시다.

# 정점(Vertex)과 간선(Edge)을 명시적으로 정의
class Graph:
    def __init__(self):
        self.vertices = set()  # 정점들의 집합
        self.edges = []        # 간선들의 리스트

    def add_vertex(self, v):
        # 정점 추가
        self.vertices.add(v)

    def add_edge(self, v1, v2):
        # 간선 추가 (두 정점을 연결)
        self.edges.append((v1, v2))
        self.vertices.add(v1)
        self.vertices.add(v2)

# 그래프 생성 및 사용
g = Graph()
g.add_edge('서울', '부산')
g.add_edge('서울', '대전')
print(f"정점: {g.vertices}")  # {'서울', '부산', '대전'}
print(f"간선: {g.edges}")     # [('서울', '부산'), ('서울', '대전')]

김개발 씨는 박시니어 씨와 함께 화이트보드 앞에 섰습니다. 박시니어 씨가 마커를 들고 동그라미 세 개를 그렸습니다.

"자, 이 동그라미 하나하나를 정점이라고 해요. 영어로는 Vertex, 복수형은 Vertices죠.

개발자들 사이에서는 **노드(Node)**라는 말을 더 많이 쓰기도 해요." 그리고 동그라미 사이를 선으로 연결했습니다. "이 선들이 바로 간선이에요.

영어로는 Edge라고 하죠." 정점은 마치 도시와 같습니다. 서울, 부산, 대전이라는 도시가 있다고 생각해보세요.

각 도시가 하나의 정점입니다. 그리고 이 도시들을 연결하는 고속도로가 간선입니다.

정점에는 데이터를 담을 수 있습니다. 단순히 이름만 저장할 수도 있고, 복잡한 객체를 저장할 수도 있습니다.

소셜 네트워크에서는 사용자 정보가 정점에 담기고, 지도 애플리케이션에서는 장소 정보가 정점에 담깁니다. 간선은 정점 사이의 관계를 나타냅니다.

"A와 B가 친구다", "서울에서 부산으로 갈 수 있다", "이 웹페이지에서 저 웹페이지로 링크가 있다"와 같은 관계를 표현합니다. 위의 코드에서 vertices는 집합(set)으로, edges는 리스트로 구현했습니다.

정점은 중복되면 안 되니까 집합을 사용했고, 간선은 순서대로 저장하기 위해 리스트를 사용했습니다. add_edge 메서드를 보면 흥미로운 점이 있습니다.

간선을 추가할 때 두 정점도 자동으로 추가됩니다. 실무에서도 이런 방어적인 코딩이 중요합니다.

존재하지 않는 정점 사이에 간선을 추가하려 할 때 오류가 나지 않도록 말이죠. 그래프의 크기는 보통 정점의 개수 V와 간선의 개수 E로 표현합니다.

알고리즘 복잡도를 분석할 때 O(V + E)처럼 표기하는데, 이때 V와 E가 바로 정점과 간선의 개수입니다. 김개발 씨가 고개를 끄덕였습니다.

"정점과 간선, 이 두 가지만 기억하면 되는 거군요. 생각보다 단순하네요!"

실전 팁

💡 - 정점(Vertex)과 노드(Node)는 같은 의미로 사용됩니다

• 그래프의 복잡도는 보통 O(V + E)로 표현합니다 (V: 정점 수, E: 간선 수)

---

3. 그래프 이론과 네트워크 분석

다음 날, 김개발 씨는 궁금증이 생겼습니다. "그래프가 도대체 어디서 나온 개념이에요?" 박시니어 씨가 흥미로운 역사 이야기를 들려주었습니다.

"18세기 수학자 오일러가 다리 건너기 문제를 풀면서 시작됐어요."

그래프 이론은 1736년 오일러의 쾨니히스베르크 다리 문제에서 시작되었습니다. 현대에 와서 그래프 이론은 네트워크 분석의 핵심 도구가 되었습니다.

소셜 네트워크, 교통망, 인터넷 등 수많은 분야에서 활용됩니다.

다음 코드를 살펴봅시다.

import networkx as nx

# NetworkX로 그래프 생성 및 분석
G = nx.Graph()

# 소셜 네트워크 예시: 친구 관계 추가
G.add_edges_from([
    ('철수', '영희'), ('철수', '민수'),
    ('영희', '민수'), ('영희', '지영'),
    ('민수', '지영'), ('지영', '현우')
])

# 네트워크 분석: 각 노드의 중요도 계산
degree = dict(G.degree())  # 연결된 간선 수
print(f"연결 수: {degree}")
# {'철수': 2, '영희': 3, '민수': 3, '지영': 3, '현우': 1}

# 가장 영향력 있는 사람 찾기
most_connected = max(degree, key=degree.get)
print(f"가장 연결이 많은 사람: {most_connected}")  # 영희, 민수, 지영 중 하나

박시니어 씨가 커피를 한 모금 마시며 이야기를 시작했습니다. "1736년, 프로이센의 쾨니히스베르크라는 도시에 재미있는 문제가 있었어요." 그 도시에는 프레겔 강이 흐르고, 강 위에 7개의 다리가 놓여 있었습니다.

시민들 사이에서 이런 질문이 돌았습니다. "모든 다리를 정확히 한 번씩만 건너서 산책할 수 있을까?" 수학자 레온하르트 오일러는 이 문제를 풀기 위해 도시를 단순화했습니다.

땅을 점으로, 다리를 선으로 표현한 것입니다. 이것이 바로 그래프 이론의 시작이었습니다.

결론적으로 오일러는 이 산책이 불가능하다는 것을 증명했습니다. "그게 지금 우리가 쓰는 그래프랑 무슨 관계가 있어요?" 김개발 씨가 물었습니다.

오일러가 만든 이 추상화 방법은 현대에 와서 네트워크 분석이라는 거대한 분야로 발전했습니다. 페이스북의 친구 추천, 구글의 검색 순위, 전염병 확산 예측까지 모두 그래프 이론에 기반합니다.

위의 코드에서 사용한 NetworkX는 파이썬에서 가장 널리 쓰이는 그래프 분석 라이브러리입니다. 복잡한 네트워크 분석을 단 몇 줄로 수행할 수 있습니다.

코드를 살펴보면, 먼저 친구 관계를 간선으로 추가했습니다. 철수와 영희가 친구, 철수와 민수가 친구...

이런 식으로요. 그 다음 degree 함수로 각 사람이 몇 명과 연결되어 있는지 계산했습니다.

이것을 **차수(Degree)**라고 합니다. 소셜 네트워크에서 차수가 높은 사람은 많은 사람과 연결된, 이른바 "인싸"입니다.

마케팅에서는 이런 사람을 인플루언서라고 부르죠. 실제 기업에서는 이보다 훨씬 정교한 분석을 수행합니다.

중심성(Centrality), 클러스터링 계수(Clustering Coefficient), 최단 경로 등 다양한 지표를 활용합니다. 김개발 씨의 눈이 반짝였습니다.

"그러니까 친구 추천 기능도 이런 네트워크 분석으로 구현할 수 있는 거군요!"

실전 팁

💡 - NetworkX 라이브러리를 사용하면 복잡한 네트워크 분석을 쉽게 할 수 있습니다

• 차수(Degree)는 한 노드에 연결된 간선의 수로, 중요도를 나타내는 기본 지표입니다

---

4. 인접 행렬과 인접 리스트

"그래프를 코드로 어떻게 저장하나요?" 김개발 씨가 질문했습니다. 박시니어 씨는 두 가지 방법을 보여주었습니다.

"인접 행렬과 인접 리스트, 각각 장단점이 있어요."

**인접 행렬(Adjacency Matrix)**은 2차원 배열로 그래프를 표현합니다. **인접 리스트(Adjacency List)**는 각 정점마다 연결된 정점들의 리스트를 저장합니다.

간선이 적으면 리스트가, 많으면 행렬이 효율적입니다.

다음 코드를 살펴봅시다.

# 방법 1: 인접 행렬 (2차원 배열)
# 정점: 0, 1, 2, 3
adj_matrix = [
    [0, 1, 1, 0],  # 0번 정점: 1, 2와 연결
    [1, 0, 1, 1],  # 1번 정점: 0, 2, 3과 연결
    [1, 1, 0, 0],  # 2번 정점: 0, 1과 연결
    [0, 1, 0, 0]   # 3번 정점: 1과 연결
]

# 0번과 1번이 연결되어 있는지 확인: O(1)
print(f"0-1 연결: {adj_matrix[0][1] == 1}")  # True

# 방법 2: 인접 리스트 (딕셔너리)
adj_list = {
    0: [1, 2],     # 0번 정점의 이웃
    1: [0, 2, 3],  # 1번 정점의 이웃
    2: [0, 1],     # 2번 정점의 이웃
    3: [1]         # 3번 정점의 이웃
}

# 1번 정점의 모든 이웃 탐색: O(이웃 수)
print(f"1의 이웃: {adj_list[1]}")  # [0, 2, 3]

박시니어 씨가 화이트보드를 둘로 나누었습니다. 왼쪽에는 격자 모양을, 오른쪽에는 목록 모양을 그렸습니다.

"그래프를 컴퓨터 메모리에 저장하는 방법은 크게 두 가지예요. 하나는 인접 행렬, 다른 하나는 인접 리스트입니다." 인접 행렬은 마치 엑셀 표와 같습니다.

행과 열 모두 정점을 나타내고, 두 정점이 연결되어 있으면 1, 아니면 0을 저장합니다. 4개의 정점이 있다면 4x4 크기의 표가 필요합니다.

"0번 정점과 1번 정점이 연결되어 있는지 알고 싶으면요?" 박시니어 씨가 물었습니다. "matrix[0][1]만 확인하면 돼요.

딱 한 번에 알 수 있죠. 이걸 **O(1)**이라고 해요." 반면 인접 리스트는 각 정점마다 "내 이웃 목록"을 따로 저장합니다.

0번 정점의 이웃은 [1, 2], 1번 정점의 이웃은 [0, 2, 3]... 이런 식으로요.

"그럼 인접 리스트에서 연결 여부를 확인하려면요?" 김개발 씨가 물었습니다. "목록을 쭉 훑어봐야 해요.

이웃이 k개면 최대 k번 확인해야 하죠. 하지만 '이 정점의 모든 이웃'을 알고 싶을 때는 리스트가 더 빨라요." 두 방법의 메모리 사용량도 다릅니다.

인접 행렬은 항상 V x V 크기의 공간이 필요합니다. 정점이 1000개면 1,000,000칸이 필요하죠.

인접 리스트는 실제 간선 수만큼만 저장하면 됩니다. 실무에서는 어떤 걸 써야 할까요?

희소 그래프(간선이 적은 그래프)에서는 인접 리스트가, 밀집 그래프(간선이 많은 그래프)에서는 인접 행렬이 유리합니다. 소셜 네트워크를 예로 들어볼까요?

페이스북에 10억 명의 사용자가 있지만, 한 사람당 친구는 평균 200명 정도입니다. 10억 x 10억 행렬보다는 리스트가 훨씬 효율적이겠죠.

김개발 씨가 깨달았습니다. "아, 그래서 처음에 보여주셨던 코드가 딕셔너리로 되어 있었군요.

인접 리스트였네요!"

실전 팁

💡 - 연결 여부 확인이 빈번하면 인접 행렬 O(1)이 유리합니다

• 이웃 탐색이 빈번하거나 간선이 적으면 인접 리스트가 효율적입니다
• 대부분의 실무 상황에서는 인접 리스트를 더 많이 사용합니다

---

5. 그래프의 구조와 종류

"그래프에도 종류가 있나요?" 김개발 씨가 물었습니다. 박시니어 씨는 여러 가지 그래프 그림을 그리며 설명했습니다.

"네, 방향이 있는지, 가중치가 있는지에 따라 여러 종류로 나뉘어요."

그래프는 방향 그래프와 무방향 그래프, 가중치 그래프 등으로 나뉩니다. 방향 그래프는 일방통행처럼 한쪽 방향만 연결됩니다.

가중치 그래프는 간선에 비용이나 거리 같은 값이 부여됩니다.

다음 코드를 살펴봅시다.

# 1. 무방향 그래프: 양방향 연결
undirected = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],  # A-B면 B-A도 존재
    'C': ['A', 'B']
}

# 2. 방향 그래프: 일방통행 가능
directed = {
    'A': ['B', 'C'],  # A에서 B, C로 갈 수 있음
    'B': ['C'],       # B에서 C로만 갈 수 있음
    'C': []           # C에서는 나갈 수 없음
}

# 3. 가중치 그래프: 간선에 비용 부여
weighted = {
    'A': [('B', 5), ('C', 3)],   # A-B 거리 5, A-C 거리 3
    'B': [('A', 5), ('C', 2)],   # B-C 거리 2
    'C': [('A', 3), ('B', 2)]
}

# A에서 C로 가는 비용 확인
for neighbor, cost in weighted['A']:
    if neighbor == 'C':
        print(f"A에서 C까지 비용: {cost}")  # 3

박시니어 씨가 화이트보드에 세 가지 그래프를 그렸습니다. 첫 번째는 선만 있는 그래프, 두 번째는 화살표가 있는 그래프, 세 번째는 선 위에 숫자가 적힌 그래프였습니다.

"첫 번째는 무방향 그래프예요. 친구 관계처럼 서로 대등한 관계를 나타낼 때 사용해요." A와 B가 친구라면 B와 A도 친구입니다.

이런 관계는 무방향 그래프로 표현합니다. 간선에 방향이 없어서 양쪽으로 모두 이동할 수 있습니다.

"두 번째는 방향 그래프입니다. 트위터 팔로우처럼 일방적인 관계를 표현해요." 내가 연예인을 팔로우한다고 해서 연예인이 나를 팔로우하는 건 아닙니다.

이런 관계는 방향 그래프로 표현합니다. 화살표가 가리키는 방향으로만 이동할 수 있죠.

"세 번째는 가중치 그래프예요. 도로의 거리, 항공권 가격처럼 연결에 비용이 있을 때 사용해요." 네비게이션 앱을 생각해보세요.

서울에서 부산까지 여러 경로가 있습니다. 각 도로에는 거리나 예상 시간이 있고, 앱은 가장 빠른 경로를 찾아줍니다.

이때 사용하는 것이 가중치 그래프입니다. 코드에서 가중치 그래프는 튜플로 표현했습니다.

('B', 5)는 "B로 가는데 비용이 5"라는 의미입니다. 이런 구조가 있어야 최단 경로 알고리즘을 적용할 수 있습니다.

이 외에도 사이클이 있는 그래프와 없는 그래프, 연결 그래프와 비연결 그래프 등 다양한 분류가 있습니다. 하지만 가장 기본적인 구분은 방향과 가중치입니다.

"그러면 제가 만들어야 하는 친구 추천 기능은 무방향 그래프겠네요?" 김개발 씨가 물었습니다. "맞아요!

친구 관계는 서로 대등하니까요. 만약 팔로우 기능이었다면 방향 그래프를 썼을 거예요."

실전 팁

💡 - 소셜 네트워크 친구 관계는 무방향, 팔로우 관계는 방향 그래프입니다

• 지도나 네비게이션은 가중치가 있는 방향 그래프로 모델링합니다

---

6. 자아 중심 네트워크

"친구 추천을 위해 어디서부터 시작해야 할까요?" 김개발 씨가 고민했습니다. 박시니어 씨가 답했습니다.

"특정 사용자를 중심으로 한 자아 중심 네트워크부터 분석해보세요."

**자아 중심 네트워크(Ego Network)**는 특정 노드(자아)를 중심으로 직접 연결된 이웃들과 그 관계를 추출한 부분 그래프입니다. 소셜 네트워크 분석에서 개인의 영향력과 관계 패턴을 파악하는 데 핵심적으로 사용됩니다.

다음 코드를 살펴봅시다.

import networkx as nx

def get_ego_network(graph, center_node, radius=1):
    """자아 중심 네트워크 추출"""
    # center_node를 중심으로 radius 거리 내의 노드들 추출
    ego_net = nx.ego_graph(graph, center_node, radius=radius)
    return ego_net

# 전체 소셜 네트워크 생성
G = nx.Graph()
G.add_edges_from([
    ('나', '친구1'), ('나', '친구2'), ('나', '친구3'),
    ('친구1', '친구2'), ('친구1', '지인A'),
    ('친구2', '지인B'), ('친구3', '지인C'),
    ('지인A', '모르는사람')
])

# '나'를 중심으로 한 자아 중심 네트워크
my_ego = get_ego_network(G, '나', radius=1)
print(f"1단계 이웃: {list(my_ego.nodes())}")
# ['나', '친구1', '친구2', '친구3']

# 친구 추천: 친구의 친구 중 내가 모르는 사람
friends_of_friends = get_ego_network(G, '나', radius=2)
recommendations = set(friends_of_friends.nodes()) - set(my_ego.nodes())
print(f"추천 친구: {recommendations}")  # {'지인A', '지인B', '지인C'}

김개발 씨는 드디어 친구 추천 기능의 실마리를 찾았습니다. 전체 네트워크를 분석할 필요 없이, 특정 사용자를 중심으로 한 작은 네트워크만 보면 됩니다.

"전체 그래프에서 '나'를 중심으로 뻗어나가는 부분만 잘라낸 거예요. 이걸 자아 중심 네트워크 또는 에고 네트워크라고 해요." 마치 지도에서 내 위치를 중심으로 반경 1km를 표시하는 것과 같습니다.

전체 세계 지도가 필요한 게 아니라, 내 주변만 있으면 되는 거죠. 자아 중심 네트워크에서 중심이 되는 노드를 **자아(Ego)**라고 합니다.

그리고 자아와 직접 연결된 노드들을 **알터(Alter)**라고 부릅니다. 친구들이 바로 알터입니다.

radius=1은 1단계 연결, 즉 직접 연결된 친구들만 포함합니다. radius=2로 설정하면 친구의 친구까지 포함됩니다.

바로 이 2단계 이웃 중에서 아직 친구가 아닌 사람들이 추천 대상이 됩니다. 코드에서 집합 연산을 사용한 부분을 주목하세요.

2단계 네트워크에서 1단계 네트워크를 빼면 "친구의 친구이지만 아직 내 친구가 아닌 사람들"이 남습니다. 이것이 친구 추천의 기본 원리입니다.

실제 페이스북이나 링크드인의 친구 추천도 이 원리를 기반으로 합니다. 물론 거기에 공통 관심사, 같은 학교 출신 등 여러 요소를 더해서 정교하게 만들지만, 핵심은 자아 중심 네트워크 분석입니다.

자아 중심 네트워크 분석은 친구 추천 외에도 다양하게 활용됩니다. 특정 인플루언서의 영향력 범위 측정, 정보 확산 경로 분석, 커뮤니티 탐지 등에 사용됩니다.

김개발 씨가 환하게 웃었습니다. "이제 어떻게 구현해야 할지 감이 와요!"

실전 팁

💡 - radius 값을 조절해 분석 범위를 조정할 수 있습니다

• 친구 추천은 2단계 이웃에서 1단계 이웃을 뺀 집합입니다
• 공통 친구 수가 많을수록 더 좋은 추천 후보입니다

---

7. 그래프 표현 방식 선택

프로젝트 마감이 다가왔습니다. 김개발 씨는 최종적으로 어떤 방식으로 그래프를 구현할지 결정해야 했습니다.

"인접 행렬로 할까요, 인접 리스트로 할까요?" 박시니어 씨가 선택 기준을 알려주었습니다.

그래프 표현 방식은 데이터의 특성과 주요 연산에 따라 선택해야 합니다. 간선 밀도, 주요 연산의 빈도, 메모리 제약을 고려해서 최적의 방식을 선택합니다.

실무에서는 대부분 인접 리스트를 기본으로 하고, 필요시 행렬로 변환합니다.

다음 코드를 살펴봅시다.

class GraphWithBothRepresentations:
    """상황에 따라 두 표현 방식을 모두 활용하는 그래프"""

    def __init__(self, vertices):
        self.V = vertices
        # 기본: 인접 리스트 (메모리 효율)
        self.adj_list = {v: [] for v in range(vertices)}
        # 필요시 생성: 인접 행렬 (빠른 조회)
        self._matrix = None

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)
        self._matrix = None  # 행렬 캐시 무효화

    def get_neighbors(self, v):
        # 이웃 탐색: 리스트가 효율적
        return self.adj_list[v]

    def is_connected(self, u, v):
        # 연결 확인: 행렬이 효율적
        if self._matrix is None:
            self._build_matrix()
        return self._matrix[u][v] == 1

    def _build_matrix(self):
        self._matrix = [[0] * self.V for _ in range(self.V)]
        for u in self.adj_list:
            for v in self.adj_list[u]:
                self._matrix[u][v] = 1

# 사용 예시
g = GraphWithBothRepresentations(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
print(f"1의 이웃: {g.get_neighbors(1)}")  # [0, 2]
print(f"0-2 연결: {g.is_connected(0, 2)}")  # False

김개발 씨는 지금까지 배운 내용을 정리했습니다. 인접 행렬은 연결 확인이 빠르고, 인접 리스트는 메모리를 적게 쓰면서 이웃 탐색이 빠릅니다.

그렇다면 어떤 걸 선택해야 할까요? 박시니어 씨가 세 가지 기준을 제시했습니다.

첫째, 간선의 밀도입니다. 정점 V개에서 가능한 최대 간선 수는 V(V-1)/2입니다.

실제 간선이 이 값에 가까우면 밀집 그래프, 훨씬 적으면 희소 그래프입니다. 희소 그래프에서는 인접 리스트가 압도적으로 유리합니다.

둘째, 주요 연산의 종류입니다. "A와 B가 연결되어 있나?"를 자주 물어본다면 행렬이 좋습니다.

"A의 모든 친구는?"을 자주 물어본다면 리스트가 좋습니다. 셋째, 메모리 제약입니다.

정점이 100만 개면 행렬은 1조 개의 칸이 필요합니다. 이건 현실적으로 불가능합니다.

이런 경우 리스트 외에는 선택지가 없습니다. 위의 코드는 실무에서 자주 쓰는 하이브리드 패턴입니다.

기본적으로 인접 리스트를 사용하고, 연결 확인이 필요할 때만 행렬을 생성합니다. 행렬은 **지연 생성(Lazy Initialization)**으로 만들어서 실제로 필요할 때까지 메모리를 절약합니다.

_matrix = None으로 시작해서 is_connected가 호출될 때 비로소 행렬을 만듭니다. 그리고 간선이 추가되면 행렬 캐시를 무효화합니다.

이렇게 하면 두 방식의 장점을 모두 활용할 수 있습니다. 김개발 씨는 최종적으로 인접 리스트를 선택했습니다.

소셜 네트워크는 전형적인 희소 그래프이고, 친구 추천은 이웃 탐색이 주요 연산이기 때문입니다. 프로젝트 발표 날, 팀장님이 물었습니다.

"왜 이 방식을 선택했어요?" 김개발 씨는 자신 있게 대답했습니다. "소셜 네트워크는 희소 그래프이고, 친구 추천은 이웃 탐색 위주라서 인접 리스트가 최적입니다.

메모리 효율도 높고요." 팀장님이 흡족해하며 고개를 끄덕였습니다. 박시니어 씨도 뒤에서 엄지를 들어 보였습니다.

실전 팁

💡 - 대부분의 실제 네트워크는 희소 그래프이므로 인접 리스트가 기본 선택입니다

• 연결 확인이 빈번하다면 인접 행렬을 캐시로 함께 사용하는 것을 고려하세요
• NetworkX 같은 라이브러리는 내부적으로 최적화된 하이브리드 구조를 사용합니다

---

이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!