그래프와 관련된 용어와 자료구조, 알고리즘을 정리합니다.
목차
- 용어 정리
- 인접 행렬, 인접 리스트
- 관련 알고리즘
용어 정리
graph: 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
vertex: 정점
adjacent vertex: 특정 정점에 직접 연결된 정점
edge: 방향이 없는 그래프에서 두 정점을 연결하는 간선
degree: 정점에 연결된 간선의 수
in-degree: 정점으로 들어오는 간선의 수 (방향이 있는 그래프)
out-degree: 정점에서 나가는 간선의 수 (방향이 있는 그래프)
cycle: 특정 정점에서 출발하여 원래 정점으로 돌아오는 경로
weighted graph: 간선에 가중치 값이 매겨진 그래프
네트워크 모델(network model): 현실 세계의 연결 관계를 수학적으로 표현한 것.
예시
- 도로망: 도시(정점), 도로(간선)
- 소셜 네트워크: 사람(정점), 친구 관계(간선)
- 데이터 흐름: 컴퓨터(정점), 패킷 경로(간선)
순환 그래프(Cyclic Graph): 출발점에서 간선을 따라가면 다시 자기 자신으로 돌아올 수 있는 그래프.
탐색 시 방문한 노드를 체크하지 않으면 무한 루프 위험이 있음.
비순환 그래프(Acyclic Graph): 출발점에서 어떠한 경로로도 자기 자신으로 돌아올 수 없는 그래프.
방향이 있는 비순환 그래프(Directed Acyclic Graph): 방향이 있고 어떠한 경로로도 자기 자신으로 돌아올 수 없는 그래프.
순서가 있는 의존 관계로 표현이 가능하고 사이클이 생기면 순서가 꼬였다고 볼 수 있다.
무방향 그래프(Undirected Graph): 간선에 방향이 없고, 양방향 이동
방향 그래프(Directed Graph): 간선에 방향이 있고, 일방향 이동
(1 -> 2)과 (2 -> 1)은 다른 간선이다.
연결 그래프(Connected Graph): 모든 정점으로 이동하는 경로가 존재하는 그래프
비연결 그래프(Disconnected Graph): 특정 정점 사이로 이동 가능한 경로가 없는 그래프.
그래프가 여러 개의 sub-graph로 나뉘어 있음.
완전 그래프(Complete Graph): 모든 정점이 서로 직접 연결된 그래프.
정점이 n개 일 때, (간선의 수) E = n * (n - 1) / 2
인접 행렬(Adjacency Matrix)
그래프를 2차원 배열로 표현
** V: 정점의 수
시간복잡도: O(V²)
공간복잡도: O(V²)
방향 그래프(Directed Graph): graph[a][b] !== graph[b][a]
대칭성 없음.
| A | B | C | |
| A | 0 | 1 | 0 |
| B | 0 | 0 | 1 |
| C | 0 | 0 | 0 |
무방향 그래프(Undirected Graph): graph[a][b] == graph[b][a]
대칭성 있음.
| A | B | C | |
| A | 0 | 1 | 0 |
| B | 1 | 0 | 1 |
| C | 0 | 1 | 0 |
인접 리스트(Adjacency List)
** V: 정점의 수
** E: 간선의 수
시간복잡도: O(E)
공간복잡도: O(V + E)
정점이 많고 간선이 적은 희소 그래프(sparse graph)에서 비효율적.
방향 그래프(Directed Graph)
A: [B]
B: [C]
C: [ ]
무방향 그래프(Undirected Graph)
A: [B]
B: [A, C]
C: [B]
관련 알고리즘
탐색 알고리즘(Graph Traversal)
- DFS: 그래프의 한 노드에서 시작해 최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 돌아와서 다른 경로를 탐색.
- BFS: 그래프의 한 노드에서 시작해 가까운 노드들을 차례대로 탐색.
최단 경로 알고리즘
- 다익스트라(Dijkstra): 한 노드에서 다른 모든 노드까지의 최단 경로. (음수 가중치 없는 그래프)
- 플로이드-와샬(Floyd-Warshall): 그래프 내의 모든 노드 간 최단 경로.
최소 신장 트리 (Minimum Spanning Tree)
- 프림(Prim): 하나의 노드에서 시작해서 점차 확장하며 최소 간선 수로 연결 그래프 생성.
- 크루스칼(Kruskal): 가중치가 가장 낮은 간선부터 선택하며 연결 그래프 생성. (with Union & Find)
순서 결정 알고리즘
- 위상정렬(Topological Sort): 방향성은 있고 사이클이 없는 그래프에서 순서를 결정.
** 각 알고리즘의 상세한 동작원리와 문제를 하나씩 풀어서 링크로 연결시킬 예정입니다!
