그래프

그래프(Graph) 자료구조

그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료구조로, 현실 세계의 다양한 관계를 표현하는 데 사용된다. 예를 들어 소셜 네트워크, 지도 길찾기, 네트워크 구조 등이 모두 그래프를 기반으로 한다.

---

 1. 그래프의 기본 개념

정점(Vertex)

그래프에서 데이터가 저장되는 기본 단위, 즉 점.

간선(Edge)

정점과 정점을 연결하는 선. 관계를 표현.

 그래프의 표현 방법

1. 무방향 그래프 (Undirected Graph)
   • (간선의) 방향이 없는 그래프
2. 방향 그래프 (Directed Graph, Digraph)
   • 방향성이 있는 그래프
   • A → B 와 B → A는 다른 간선
3. 가중치 그래프 (Weighted Graph)
   • 간선에 비용, 거리, 시간 등의 가중치 값이 붙음
4. 루트없는 트리(Unrooted Tree)
   
   • 간선을 통해 정점 간 잇는 방법이 한가지인 그래프(*트리의 정의)
5. 이분 그래프 (Bipartite Graph)
   • 그래프의 정점을 겹치지 않게 두 그룹으로 나눈 후 다른 그룹끼리만 간선이 존재하게 분할할 수 있는 그래프
6. 사이클없는 방향 그래프(Directed Acylic Graph)
   • 정점에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 없는 그래프

---

 2. 그래프의 표현 방식

 2.1 인접 행렬 (Adjacency Matrix)

2차원 배열로 정점 간의 간선의 존재 여부를 1 또는 0으로 표현한다.

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

• 장점: 구현 간단, 두 노드 연결 여부를 O(1)에 확인
• 단점: 노드가 많을 때 공간 낭비가 큼 (O(N²))

---

 2.2 인접 리스트 (Adjacency List)

각 정점마다 연결된 정점 리스트를 저장.

A: B
B: A, C
C: B

• 장점: 메모리 효율적, 실제 연결만 저장
• 단점: 두 노드 연결 여부를 찾는 데 O(N) 간선이 매우 적으면 비효율적

---

3. 그래프 탐색 알고리즘

그래프를 순회하는 대표 방식은 두 가지.

 3.1 DFS (Depth-First Search, 깊이 우선 탐색)

• 한 방향으로 끝까지 파고들고, 막히면 뒤로 돌아가 탐색
• 재귀 또는 스택 사용

3.2 BFS (Breadth-First Search, 너비 우선 탐색)

• 가까운 정점부터 탐색
• 큐(Queue) 사용

---

4. 그래프의 실제 활용 예

SNS(친구 관계)

• 사용자 = 정점
• 친구 관계 = 간선

길찾기(네비게이션)

• 장소 = 정점
• 도로 = 간선(가중치 = 거리)

컴퓨터 네트워크

• 라우터 = 정점
• 연결 케이블 = 간선