[100일의 IT 초보 탈출] #53 그래프(Graph) _ 관계를 표현하는 가장 유연한 구조

오늘은 무엇을 배우게 될까요?

 

DFS, BFS는 그래프(Graph)를 탐색하기 위한 알고리즘이었죠.

하지만 정작 그래프가 뭔지, 어떻게 생겼는지는 제대로 이야기하지 않았습니다.

 

그래프는 실생활에서 수없이 많이 등장하는 구조입니다.

오늘은 그래프의 개념, 구성 요소, 종류, 표현 방식, 그리고 활용 예시까지 살펴보겠습니다.

 

---

 

그래프란?

 

그래프(Graph)는

정점(Vertex, 노드)과 간선(Edge)으로 이루어진 자료구조입니다.

→ 정점끼리의 관계를 표현하는 구조입니다.

 

예를 들어, 사람 간의 친구 관계, 도시 간의 연결, 컴퓨터 네트워크, 소셜미디어 팔로우 등

“관계”가 있는 거의 모든 것을 그래프로 나타낼 수 있습니다.

 

 

---

그래프의 구성 요소

구성 요소설명

정점(Vertex)	정보를 담는 기본 단위 (ex: 사람, 도시 등)
간선(Edge)	두 정점을 잇는 연결선 (ex: 친구 관계, 도로 등)

 

---

그래프의 종류

구분 기준과 종류 설명

방향성	무방향 그래프	A → B와 B → A가 동일한 관계 (예: 친구)
	방향 그래프	A → B는 있지만 B → A는 없을 수도 있음 (예: 팔로우)
순환성	순환 그래프	경로를 따라 다시 출발점으로 돌아올 수 있음
	비순환 그래프(DAG)	다시 돌아오는 경로가 없음 (위상 정렬용)
가중치	가중치 그래프	간선에 숫자(비용, 거리 등)가 있음 (예: 지도)
	비가중치 그래프	간선은 단순 연결만 의미

 

---

그래프 표현 방법

 

1. 인접 행렬 (Adjacency Matrix)

A	0	1	1
B	1	0	0
C	1	0	0

 

• 간선을 2차원 배열로 표현
• 정점 수가 적고 밀접하게 연결되어 있을 때 유리
• 공간 복잡도: O(V²)

 

 

1. 인접 리스트 (Adjacency List)

graph = {
    'A': ['B', 'C'],
    'B': ['A'],
    'C': ['A']
}

 

• 각 정점이 연결된 노드 리스트를 가짐
• 정점이 많고 간선이 적을 때 효율적
• 공간 복잡도: O(V + E)

 

---

그래프를 언제 사용하나요?

분야활용 예

컴퓨터 네트워크	라우팅, IP 연결 구조
SNS	친구/팔로우 관계
길찾기	도시 간 최단 경로, 지도 탐색
일정 관리	작업 순서 결정 (위상 정렬)
추천 시스템	유사 사용자 기반 추천
인공지능	상태 전이 그래프, 강화학습

 

---

 

 

그래프 예시: 도시 간 연결

 

• 정점: 서울, 부산, 대전
• 간선: 도로
• 가중치: 거리 (km)

graph = {
    '서울': [('대전', 140), ('부산', 400)],
    '대전': [('서울', 140), ('부산', 260)],
    '부산': [('서울', 400), ('대전', 260)]
}

 

---

그래프의 활용이 중요한 이유

 

그래프는 탐색 기반 알고리즘의 시작점입니다.

 

• 최단 거리를 구하려면 → 그래프 + BFS/Dijkstra
• 모든 경로 탐색을 하려면 → 그래프 + DFS
• 의존 관계를 따져야 하면 → 그래프 + 위상 정렬

 

즉, 문제 자체를 그래프 형태로 추상화할 수 있어야

그 위에 적절한 알고리즘을 쌓을 수 있습니다.

 

---

한 줄 요약

 

👉 그래프는 관계와 연결을 표현하기 위한 자료구조로,

실생활 문제를 알고리즘으로 해결할 때 꼭 필요한 뼈대입니다.