연결 관계를 표현하는 자료구조
네트워크, 운영체제 등 다양한 분야에서 사용
그래프의 종류와 구현
📌 그래프 기본 개념
정점이라 불리는 데이터를 간선 혹은 링크로 연결한 형태의 자료구조
- 정점(Vertex): 데이터를 표현하는 노드
- 간선(Edge) 또는 링크(Link): 정점 간의 연결을 나타냄
노드와 노드를 간선으로 연결한 트리도 그래프의 일종
트리는 사이클을 형성하지 않고 연결된 노드 간에 상하 관계를 가지고 있지만, 일반적인 그래프는 사이클을 형성할 수 있고, 이웃한 정점끼리 상하 관계를 가지지 않습니다.
> 사이클: 특정 정점에서 출발하여 다시 같은 정점으로 돌아오는 경로
그래프는 다양한 연결 관계를 표현하는 자료구조로, 지하철 노선도처럼 역과 역을 연결하는 경로, 컴퓨터 네트워크처럼 통신 기기와 그들 간의 연결을 모두 그래프 형태로 표현할 수 있음
그래프의 종류
📌 연결 그래프 / 비연결 그래프
가장 기본적인 그래프 유형으로 임의의 두 정점 사이를 잇는 경로가 있느냐 없느냐에 따라 나뉨
연결 그래프: 그래프의 모든 두 정점 간에 경로가 존재하는 그래프
쉽게 말해, 2개의 아무 정점이나 골라 간선(들)으로 서로를 이을 수 있다면 연결 그래프
비연결 그래프: 그래프의 일부 정점 사이에는 경로가 존재하지 않는 그래프
📌 방향 그래프 / 무방향 그래프
간선에 방향이 있느냐 없느냐에 따라 나뉨
방향 그래프: 간선에 방향이 있는 그래프
무방향 그래프: 간선에 방향이 없는 그래프
📌 가중치 그래프
간선에 가중치(비용)가 부여된 그래프
예를 들어, 지하철 역을 정점, 역과 역 사이를 연결하는 경로를 간선으로 보는 그래프에서는 역과 역 사이의 거리를 가중치로 설정할 수 있음. 이 가중치는 양수일 수도 있고, 음수일 수도 있음
📌 서브그래프
특정 그래프의 정점과 간선의 일부분으로 구성된 그래프
그래프 G의 일부 정점과 간선으로 구성된 그래프 H는 G의 서브그래프
인접 행렬 기반 그래프 표현
N x N 크기의 행렬로 그래프를 표현하는 방법
여기서 N은 정점의 개수를 의미하며, N x N 행렬의 <행, 열> 값은 <출발 정점, 도착 정점>을 의미
일반적 그래프 표기:
0: 연결되지 않은 경우
1: 연결된 경우
정점 1에서 정점 2로 연결 → 1행 2열에 1을 표기
여기서 무방향이라면 무방향 그래프의 정점은 양방향으로 연결되어 있다고 간주함
여기서 무방향 그래프를 표현한 인접 헹렬의 특징은 행렬의 대각선 요소를 기준으로 연결 관계가 대칭을 이룬다는 점
인접행렬은 이렇게 2차원 배열로 연결 관계를 명확히 표현
가중치 그래프 인접 행렬 표현
가중치 그래프의 경우, 0과 1 대신 가중치를 사용하여 연결을 나타냄
정점 1에서 정점 2로 가는 간선의 가중치가 2 → 1행 2열에 2를 표기
인접 리스트 기반 그래프 표현
그래프의 특정 정점과 연결된 정점들을 연결리스트로 표현하는 방법
각각의 정점마다 연결 리스트를 가지는데, 특정 정점에서 나가는 간선에 연결된 정점들을 연결 리스트의 노드로 삼는다는 의미
정점 1에서 정점 2로 연결 → 정점 1 연결 리스트의 노드로 정점 2를 추가
가중치 그래프 인접 리스트 표현
인접 리스트 기반 그래프 표현으로 무방향 그래프를 표현하는 것은 인접 행렬을 이용한 그래프 표현과 유사함
정점 간의 연결 관계를 표현할 때 양방향으로 연결한다고 생각하면 됨
깊이 우선 탐색과 너비 우선 탐색
각각의 탐색 방법은 그래프를 순회하는 방식에서 차이를 보이며, 알고리즘의 목적과 상황에 따라 적합한 방법을 선택해야함
깊이 우선 탐색 (DFS, Depth First Search)
그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊게 탐색하기를 반복하는 탐색 방법
DFS 사용 자료구조
- DFS 알고리즘을 구현할 때 유용하게 사용되는 자료구조로 배열과 스택이 있음
- 배열은
특정 정점의 방문 여부를 확인하기 위해 사용 - 스택은 방문 중
뒤로가기가 필요할 때 사용
DFS의 예시
- 정점 a부터 탐색을 시작하며, 인접한 정점이 2개 이상일 경우에는 알파벳 순으로 탐색한다고 가정
- '아직 한 번도 방문하지 않은 정점'은
미방문 정점이라고 지칭
| 순서 | 설명 | 배열 상태 | 스택 상태 |
|---|---|---|---|
| 1 | 정점 a를 방문. 정점 a와 연결된 미방문 정점은 b, c, d | a | [a] (스택에 a PUSH) |
| 2 | 정점 b를 방문. 정점 b와 연결된 미방문 정점은 e | a, b | [a, b] (스택에 b PUSH) |
| 3 | 정점 e를 방문. 정점 e와 연결된 미방문 정점은 없음 | a, b, e | [a, b, e] (스택에 e PUSH) |
| 4 | 정점 e에서 정점 b로 돌아감. 정점 b와 연결된 미방문 정점은 없음 | a, b, e | [a, b] (스택 POP) |
| 5 | 정점 b에서 정점 a로 돌아감. 정점 a와 연결된 미방문 정점은 c, d | a, b, e | [a] (스택 POP) |
| 6 | 정점 c를 방문. 정점 c와 연결된 미방문 정점은 f | a, b, e, c | [a, c] (스택에 c PUSH) |
| 7 | 정점 f를 방문. 정점 f와 연결된 미방문 정점은 d | a, b, e, c, f | [a, c, f] (스택에 f PUSH) |
| 8 | 정점 d를 방문. 정점 d와 연결된 미방문 정점은 없음 | a, b, e, c, f, d | [a, c, f, d] (스택에 d PUSH) |
| 9 | 정점 d에서 정점 f로 돌아감. 정점 f와 연결된 미방문 정점은 없음 | a, b, e, c, f, d | [a, c, f] (스택 POP) |
| 10 | 정점 f에서 정점 c로 돌아감. 정점 c와 연결된 미방문 정점은 없음 | a, b, e, c, f, d | [a, c] (스택 POP) |
| 11 | 정점 c에서 정점 a로 돌아감. 정점 a와 연결된 미방문 정점은 없음 | a, b, e, c, f, d | [a] (스택 POP) |
| 12 | 더 이상 방문하지 않은 미방문 정점이 없으므로 탐색 종료 | a, b, e, c, f, d | [] (스택 POP) |
너비우선탐색 (BFS, Breadth First Search)
최대한 넓게 탐색하기를 반복하는 방법
인접한 모든 정점들을 방문하고, 방문한 정점들과 연결된 모든 정점들을 방문하고, 또 방문한 정점들과 연결된 모든 정점들을 방문하기를 반복하는 탐색 방법이라고 할 수 있음
DFS와 동일하게 정점 a부터 탐색을 시작하며, 인접한 정점이 2개 이상일 경우에는 알파벳 순으로 탐색한다고 가정
DFS 알고리즘을 구현할 때 스택과 배열을 사용했다면 BFS 알고리즘에서는 배열과 큐를 사용
배열은 DFS에서의 용래와 같이 특정 정점의 방문 여부를 확인하기 위해 사용하고, 큐는 연결된 정점들을 저장하기 위해 사용
| 순서 | 설명 | 배열 상태 | 큐 상태 |
|---|---|---|---|
| 1 | 정점 a를 방문 | a | [] |
| 2 | 정점 a와 연결된 미방문 정점은 b, c, d | a | [b, c, d] (큐에서 a 디큐 b, c, d 인큐) |
| 3 | 정점 b, c, d를 차례로 방문 | a, b, c, d | [b, c, d] |
| 4 | 정점 b와 연결된 미방문 정점은 e | a, b, c, d | [c, d, e] (큐에서 b 디큐, e 인큐) |
| 5 | 정점 e를 방문 | a, b, c, d, e | [c, d, e] |
| 6 | 정점 c와 연결된 미방문 정점은 f | a, b, c, d, e | [d, e, f] (큐에서 c 디큐, f 인큐) |
| 7 | 정점 f를 방문 | a, b, c, d, e, f | [d, e, f] |
| 8 | 정점 d와 연결된 미방문 정점은 없음 | a, b, c, d, e, f | [e, f] (큐에서 d 디큐) |
| 9 | 정점 e와 연결된 미방문 정점은 없음 | a, b, c, d, e, f | [f] (큐에서 e 디큐) |
| 10 | 정점 f와 연결된 미방문 정점은 없음 | a, b, c, d, e, f | [] (큐에서 f 디큐) |
| 11 | 더 이상 방문하지 않은 미방문 정점이 없으므로 탐색 종료 | a, b, c, d, e, f | [] |
깊이우선탐색(DFS)은 하나의 경로를 끝까지 탐색하는 방식으로, 트리의 순회나 경로 찾기에 유용
너비우선탐색(BFS)은 최단 경로를 찾거나 그래프의 레벨을 탐색하는 데 유용
두 방법 모두 그래프의 순회와 탐색에서 중요한 역할을 하며, 문제의 특성에 맞춰 z적합한 방법을 선택해야함
최단 경로 알고리즘
한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘
대표적으로 지도 서비스에서 원하는 목적지까지 이르는 최단 거리를 알려 주는 원리로도 사용됨
컴퓨터 네트워크에서도 최단 경로 알고리즘이 사용됨
지구 반대편에 있는 컴퓨터와 통신하려면 중간에 여러 네트워크 장비들을 거치게 되는데
이때 컴퓨터가 보낸 메시지는 중간에 있는 여러 네트워크 장비들을 통해 최종적으로 지구 반대편 컴퓨터에 도달
컴퓨터와 네트워크 장비를 정점, 통신 네트워크를 간선이라고 생각하면됨
다익스트라 알고리즘
간선의 가중치가 음이 아닌 수라는 가정 하에 사용 가능한 알고리즘으로 특정 정점에서 다른 모든 정점까지의 최단 거리를 구해 주는 알고리즘
또, 다익스트라 알고리즘은 작동 과정에서 특정 정점에 이르는 거리를 저장한 데이터가 함께 사용됨
📌 알고리즘 작동 과정
- 편의상 배열로 구현한다고 가정하고 `최단 거리 테이블`이라고 명명1️⃣ 최단 거리 테이블 상에서 시작 정점을 제외한 정점들은 모두 충분히 큰 수로 초기화
- 최단거리 테이블을 만들고, 시작 정점을 제외한 모든 정점은 무한히 큰 값(충분히 큰 수)로 초기화
- 시작 정점의 최단거리는 0으로 설정
2️⃣ (시작) 정점을 방문
- 시작 정점에서 시작
3️⃣ 방문한 정점과 인접한 정점들을 탐색
- 시작 정점과 연결된 인접 정점들을 차례대로 탐색
4️⃣ 경로 상의 가중치 합과 최단 거리 테이블 상의 값을 비교
- 방문한 정점과 인접한 정점들의 거리를 계산하여, 기존의 최단거리 테이블의 값과 비교
5️⃣ 최단 거리 테이블을 갱신할 수 있다면 갱신
- 만약 더 짧은 경로가 발견되면, 최단거리 테이블을 갱신
6️⃣ 방문하지 않은 정점 중 최단 거리가 가장 작은 정점을 방문
- 방문하지 않은 정점 중 최단거리 값이 가장 작은 정점을 선택하여, 그 정점을 방문
7️⃣ 더 이상 방문할 정점이 없을 때까지 3️⃣~6️⃣의 과정을 반복하고 종료
- 위 과정을 모든 정점을 방문할 때까지 반복
- 모든 정점의 최단거리 테이블이 완성되면 알고리즘이 종료
참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 4-6)
