그래프 이론 기초

1. 그래프란?

• 그래프(graph)란 여러 개의 점(정점, 노드, vertex)과 이 점들을 연결하는 선(간선, edge)으로 이루어진 자료구조입니다.
• 그래프의 예시:
  • 지하철 노선도
  • 소셜 네트워크(사람이 노드, 친구 관계가 간선)
  • 지도(도시가 노드, 도로가 간선)

2. 그래프의 구성 요소

• 정점(Vertex, Node):
• 정보를 담고 있는 점. 예: 도시, 사람, 컴퓨터 등.
• 간선(Edge):
• 정점과 정점을 연결하는 선. 예: 도로, 친구 관계, 네트워크 케이블 등.

3. 그래프의 종류

1) 방향 그래프(Directed Graph)

• 간선에 방향이 있음.
• 예: 트위터 팔로우(한쪽만 연결 가능)
• 표기: (A → B) : A에서 B로만 이동 가능

2) 무방향 그래프(Undirected Graph)

• 간선에 방향이 없음.
• 예: 페이스북 친구(양방향)
• 표기: (A — B) : A와 B는 서로 이동 가능

3) 가중치 그래프(Weighted Graph)

• 간선마다 "비용"이나 "거리" 등 숫자가 붙어 있음.
• 예: 지도에서 각 도로의 거리, 네트워크의 전송 속도 등

4) 비가중치 그래프(Unweighted Graph)

• 간선에 숫자가 없음. 단순 연결만 의미.

4. 그래프의 특징

• 인접(Adjacent):
• 두 정점이 간선으로 직접 연결되어 있으면 인접하다고 함.
• 경로(Path):
• 한 정점에서 다른 정점으로 이동하는 방법(간선의 연속)
• 사이클(Cycle):
• 시작점으로 다시 돌아오는 경로가 존재하면 사이클이 있다고 함.
• 연결 그래프(Connected Graph):
• 모든 정점이 서로 경로로 연결되어 있는 그래프.
• 비연결 그래프(Disconnected Graph):
• 일부 정점이 서로 연결되어 있지 않은 그래프.

5. 그래프의 표현 방법

• 인접 리스트(Adjacency List):메모리 효율적, 연결된 노드만 저장.
• 각 정점이 연결된 정점들의 리스트를 가짐.
• 인접 행렬(Adjacency Matrix):간선 존재 여부를 0/1(또는 가중치)로 표시.
• 빠른 연결 확인, 메모리 많이 사용.
• 정점 수가 n개면 n x n 행렬로 표현.

6. 그래프의 활용 예시

• 네비게이션(최단 경로 탐색)
• 소셜 네트워크(친구 추천, 연결 관계 분석)
• 컴퓨터 네트워크(데이터 흐름, 최적 경로)
• 스케줄링(작업 순서 결정, 위상 정렬)
• 게임(맵 탐색, AI 이동 경로)

7. 그래프 관련 용어 정리

용어 설명

정점(Vertex)	그래프의 점, 노드
간선(Edge)	정점과 정점을 연결하는 선
차수(Degree)	한 정점에 연결된 간선의 개수
경로(Path)	한 정점에서 다른 정점으로 가는 길
사이클(Cycle)	시작점으로 돌아오는 경로
연결성	모든 정점이 경로로 연결되어 있는지의 여부
트리(Tree)	사이클이 없는 연결 그래프(특수한 그래프)

8. 그래프 탐색의 필요성

그래프는 복잡한 연결 구조를 표현할 수 있으므로,

• 모든 노드 방문(탐색)
• 최단 경로 찾기
• 사이클 존재 여부 확인
• 최소 비용 네트워크 구성
• 등의 문제를 푸는 데 매우 중요합니다.

이렇게 그래프의 기본 개념, 종류, 특징, 표현 방법 등을 이해하면

그래프 알고리즘(탐색, 최단 경로, MST, 위상 정렬, 네트워크 플로우 등)을 쉽게 배울 수 있습니다!

다음 포스팅에서는 그래프 알고리즘에 대해서 설명할게요!