[알고리즘] 14. 그래프

1. 그래프(Graph)의 개념 및 표현 방법

1) 그래프란?

• 개체들과 이들 사이의 연결 관계를 표현하는 자료구조

• 복잡한 작업을 시각적으로 구조화하여 표현 가능

• 주요 요소 간의 관계, 거리, 비용 등을 나타낼 수 있음

• 선형 자료구조나 트리로 표현하기 어려운 다대다 관계를 표현하는 데 유용

• 정점(Vertices, V)과 간선(Edges, E)으로 구성됨

- G = (V, E)

- V: 그래프에 있는 정점들의 집합

- E: 정점을 연결하는 간선들의 집합

• 활용 예시: 버스 노선도, 인맥 지도

 

 

2. 그래프의 종류 및 특징

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

• 간선에 방향이 없음

• (Vi, Vj)와 (Vj, Vi)는 같은 간선

 

2) 방향 그래프(Directed Graph)

• 간선에 방향이 존재함

• Vi → Vj를 <Vi, Vj>로 표현

 

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

• 간선에 거리, 시간, 비용 등의 가중치가 존재함

 

4) DAG(Directed Acyclic Graph, 유향 비순환 그래프)

• 사이클이 없는 방향 그래프

 

5) 완전 그래프(Complete Graph)

• 모든 정점이 서로 연결된 그래프

- 무방향 그래프의 최대 간선 수: n(n-1)/2

- 방향 그래프의 최대 간선 수: n(n-1)

 

6) 부분 그래프(Subgraph)

• 원래 그래프에서 일부 정점과 간선만을 포함한 그래프

• V(G')⊆V(G), E(G’)⊆E(G)

 

7) 그래프의 경로(Path)

• 정점과 간선을 따라 이동하는 경로

• 단순 경로(Simple Path): 중복 정점이 없는 경로

 

 

3. 그래프의 표현 방법

1) 인접 행렬(Adjacent Matrix)

• 그래프의 두 정점을 연결하는 간선의 존재 여부를 행렬로 표현

• V개의 정점 → |V| × |V| 크기의 2차원 배열 사용

• 무방향 그래프: i번째 행의 합과 열의 합이 같음 (정점의 차수)

• 방향 그래프:

- 진입 차수 (in-degree): 해당 정점으로 들어오는 간선 개수

- 진출 차수 (out-degree): 해당 정점에서 나가는 간선 개수

 

2) 인접 리스트(Adjacent List)

• 각 정점에 대한 인접 정점을 연결 리스트 형태로 표현

• 장점: 필요 없는 간선을 저장하지 않아 메모리 절약 가능

• 단점: 특정 간선의 존재 여부를 확인하는 데 시간이 더 걸릴 수 있음

• 정점 차수 계산:

- 무방향 그래프: 간선 수 = 정점 차수의 합 / 2

- 방향 그래프: 간선 수 = 모든 정점의 진출 차수 합

 

 

4. 그래프 표현 방식 비교

표현 방식	메모리 사용	간선 존재 여부 확인 속도	인접 정점 탐색 속도
인접 행렬	O(V²)	O(1)	O(V)
인접 리스트	O(V + E)	O(V)	O(degree)

• 그래프의 크기와 형태에 따라 적절한 표현 방식 선택 필요

• 밀집 그래프(Dense Graph, 간선 수 많음): 인접 행렬 사용이 유리

• 희소 그래프(Sparse Graph, 간선 수 적음): 인접 리스트 사용이 유리

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.