1. 그래프의 기본 개념
✅ 그래프
정점(Vertex)와 간선(Edge)의 집합 `G = (V, E)`
개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델
그래프를 표현하는 방법
수학적으로 표현하면:
V = {0, 1, 2, 3} //정점이 0,1,2,3이 있을 때
E = {(0,2), (0,3), (1,2), (1,3)} //각 정점이 가지고 있는 관계 (한 쌍 안의 두 정점은 이어져 있다)
📍 알고리즘 문제에서 사용하는 방식
엣지 리스트를 이용해 표현하면:
4,4 //Vertex의 개수, Edge의 개수 (Vertex: 0 - 3)
0,2 //Vertex 0과 2를 연결하는 Edge
0,3
1,2
1,3
방향과 가중치에 따른 그래프 종류
- 무방향 그래프(Undirected, Non-weighted)
- 방향 그래프(Directed, Non-weighted)
- 가중치 그래프(Undirected, Weighted)
- 방향 가중치 그래프(Directed, Weighted)
특별한 그래프
(1) Self edge를 가진 그래프
G = (V,E)
V = {1, 2, 3, 4, 5, 6}
E = {..., (2,2), ..., (6,6)}2번 정점, 6번 정점은 자기 자신과 관계를 맺고 있다.
(2) Multi edge를 가진 그래프
G = (V,E)
V = {1, 2, 3, 4, 5, 6}
E = {..., (1,5), (1,5), (1,5), ..., (2,3), (2,3), ...}1번 정점과 5번 정점, 2번 정점과 3번 정점이 여러개의 관계를 맺고 있다.
복잡도(Edge의 개수)에 따른 그래프 종류
(1) 완전 그래프: 모든 정점이 서로 연결된 그래프
| 정점 개수 | n-1 | 모든 정점 n개 - 자기 자신 |
| 엣지 개수 (방향 그래프) |
n(n-1) | 모든 정점 n * 연결된 정점 개수 n-1 |
| 엣지 개수 (무방향 그래프) |
n(n-1) / 2 | 무방향 그래프의 경우 관계가 중복되는 경우를 제거하기 위해 2로 나눠준다. |
(2) 밀집 그래프: 정점 대부분이 서로 연결된 그래프
| 엣지 개수 | O(n^2) | 정점 하나에 k개 정점이 연결되어 있다고 하면, 엣지 개수는 n * k 개가 된다. 이 때 “대부분”이라고 했으므로 k는 n에 가까운 수이므로, 이를 o표기법으로 치환하면 O(n^2)로 표기할 수 있다. |
(3) 희소 그래프: 모든 정점이 상수개(대략 k개)의 정점과 연결된 그래프
| 한 정점과 연결된 정점 개수 |
O(1) | 상수 k개를 o표기법으로 치환하면 O(1)으로 표기할 수 있다. |
| 엣지 개수 | O(n) | 모든 정점 개수를 곱하면 kn이 되는데, o표기법으로 치환하면 O(n)으로 표기할 수 있다. |
2. 그래프의 용어
| Vertex(정점) | 하나의 개체를 표현하며, 원 내부의 숫자나 문자로 나타낸다. |
| Edge(엣지) | (1) 정점과 정점의 1:1 관계를 나타내며, 정점의 쌍으로 표현한다. `(0,1)` (2) 방향성이 있는 관계의 경우 `(0,1) ≠ (1,0)`, 방향성이 없는 관계의 경우 `{0,1} = {1,0}` |
| 인접(Adjacent) | 정점 u와 v가 엣지로 연결되어 있을 경우, u와 v는 인접해 있다. 예: 정점 0과 1은 인접해있다. |
| Incident | 두 엣지가 같은 정점을 공유하고 있을 경우, 두 엣지는 incident. 예: (0,1)과 (0,4)는 incident. |
| 부분 그래프(Subgraph) | G=(V,E)이고 G’=(V’,E’)일 때, V’가 V에 포함되고 E’가 E에 포함된다면, G’는 G의 부분 그래프이다. |
| 경로(Path) | 1. 정점 u에서 정점 v로 가는 경로는 다음을 만족하는 정점들의 연속체: (1) (u, i), (i, j), …, Ik, v)는 E에 포함된다. (2) 경로 (u, v) = (u, i, j, …, k, v 예: 경로 (0, 2): (0, 1, 2) 2. 물론 여러 개의 경로가 존재할 수 있다. 예: 경로 (0, 2): (0, 1, 2), (0, 1, 3, 2) … |
| 경로의 길이 (length of path) |
경로에 있는 정점 또는 엣지의 수 *가중치 그래프의 경우 경로에 있는 엣지의 가중치 합 |
| 최단 경로 (shortest path) |
여러 경로 중에서 그 길이가 최소인 경로 또는 가중치의 합이 최소인 경우 |
| 단순 경로 (simple path) |
시작 정점과 끝 정점을 제외한 모든 정점이 서로 다른 경로 |
| 순환(cycle) | 첫 번째 정점과 마지막 정점이 일치하는 단순 경로 (어떤 정점에서 출발하여 다시 그 정점으로 돌아올 수 있는 단순 경로) |
| 비순환 그래프 (acyclic graph) |
순환이 존재하지 않는 그래프 |
| 연결(connected) | 1. 두 정점 u와 v 사이에 경로가 존재할 경우, 이 두 정점은 연결되었다. 2. 어떤 그래프에 속한 모든 쌍의 정점이 연결되었을 경우, 이 그래프는 연결되었다. |
| 연결 성분 (connected component) |
연결된 부분 그래프의 최대치 (a maximal connected subgraph) |
| *트리는 연결된 비순환 그래프(connected acyclic graph)라고 이야기할 수 있다. | |
| 방향 그래프에서의 연결 | 1. 방향 그래프에서는 경로에 방향성이 추가되므로 강한 연결(strongly connected)이라고 한다. (서로 가는 길(엣지)가 존재해야만 연결되어있는 것으로, 그렇지 않으면 연결된 것이 아니다) 2. 강하게 연결된 부분 그래프의 최대치를 강한 연결 성분이라고 한다. |
| 정점의 차수 (Degree of a vertex) |
정점에 연결된 엣지의 수 |
| 신장 트리 (spanning tree) |
모든 노드가 사이클 없이 연결된 부분 그래프 1. 그래프 G=(V,E)의 부분 그래프 T=(V’,E’)가 다음의 조건을 만족할 때 T는 G의 신장 트리: (1) V’는 V와 같고 && E’는 E에 포함된다. (2) E’는 순환이 없고 && E’의 수는 n-1개이다. 2. 여러 개의 신장 트리가 존재한다. |
3. 그래프 구현
✅ 코딩에서 그래프를 구현하는 방법
그래프의 엣지 리스트를 제시한다.
정점은 `0 - (n-1)` 또는 `1 - n`으로 설정한다.
(1) 인접 행렬 (Adjacency matrix)
➡️ 정점의 개수가 n일 때, n x n 크기의 배열로 표현한다.
정점 i와 j가 연결되어 있다면 `a[i][j] = 1`
정점 i와 j가 연결되어 있지 않다면 `a[i][j] = 0`
🚧 이 때, 무방향 그래프의 행렬은 `a[i][j] == a[j][i]`를 만족하는 대칭 행렬이 된다.
(2) 인접 리스트 (Adjacency list)
➡️ n개의 연결 리스트로 표현한다: `adjLists[n]`
`adjLists[i]`는 정점 i로부터 시작하는 엣지에 연결된 정점을 연결하는 연결 리스트의 시작이다.
인접 리스트를 구현해보면:
//INPUT
4 5 //정점 개수:4, 엣지 개수:5
1 2
1 3
1 4
2 4
3 4#include <vector>
#include <algorithm>
vector<int> edge[10001];
void main() {
scanf("%d %d", &n &m);
for(i=0; i<m; i++) {
scanf("%d %d", &u &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
/*
만들어진 edge list
1: 2, 3
2: 1, 4
3: 1, 4
4: 1, 2
*/
//정렬되어 들어오지 않았을 경우를 대비해 정렬
for(i=1; i<=n; i++) {
sort(edge[i].begin(), edge[i].end());
}
}
구현 방법 간 성능 비교
모든 정점에서 인접한 정점을 출력하시오
for all vertices v in G
for all vertices w adjacent to v
report (v, w);
이중 for문을 수행해야 한다.
| 인접 행렬 | 인접 리스트 | |
| 완전/밀집 그래프 | O(n^2) | O(n^2) |
| 희소 그래프 | O(n^2) | O(n) |
⇒ 최대한 인접 리스트를 사용하는 것이 좋다.
'CS > 자료구조' 카테고리의 다른 글
| [k-mooc/자료구조] 13. 넓이 우선 탐색(BFS) (2) | 2025.08.17 |
|---|---|
| [k-mooc/자료구조] 12. 깊이 우선 탐색(DFS) (4) | 2025.08.13 |
| [k-mooc/자료구조] 10. 탐색 (6) | 2025.08.09 |
| [k-mooc/자료구조] 09. 우선 순위 큐(Priority Queue)와 힙(Heap) (4) | 2025.08.07 |
| [k-mooc/자료구조] 08. 이진 탐색 트리(Binary Search Tree) (1) | 2025.08.06 |