그래프의 개념
그래프의 유래
- 쾨니히스베르크(Konigsberg) 다리 문제
- 오일러가 그래프 개념을 도입해서 해결
- 땅과 섬 → Node (Vertex)
- 다리 → Edge (Link)
- 다리 문제 → 한 붓 그리기
- 한 붓 그리기 문제
- 홀수 개의 Edge에 연결된 Vertex의 수가 4개 이상이면 한 붓 그리기가 불가능한 도형
그래프의 정의
- 개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델
- Vertex: 꼭짓점, 정점, 노드
- Vertex는 대체를 나타냄
- Edge: 간선
- 1:1 관계, 노드의 쌍으로 표현
그래프의 표현
- 그래프를 Vertex와 Edge의 쌍으로 표현
- G = (V, E)
- 수학적 표현
- Vertex: 모든 Vertex들의 집합, V = {0, 1, 2, 3}
- Edge: Vertex 쌍들의 집합, E = {(0, 2), (0, 3), (1, 2), (1, 3)}
- 시각적 표현
- Vertex: 원과 원 내부의 기호로 표현
- Edge: Vertex와 Vertex를 연결하는 실선으로 표현
- Edge List를 이용한 표현
- 코딩 테스트에서 가장 많이 사용하는 표현
4, 4 // ─ Vertex의 수와 Edge의 수
0, 2 // ┌ 각 줄 마다
0, 3 // │ Edge를
1, 2 // │ 나타냄
1, 3 // └ (Vertex의 쌍)그래프의 종류
- 방향과 가중치에 따른 분류
- 무방향 그래프 (Graph)
- 방향 그래프 (Directed Graph)
- 가중치 그래프 (Weighted Graph)
- 방향 가중치 그래프 (Weighted Directed Graph)
- 특별한 그래프
- Self-Graph: 순환(자기 자신으로의 Edge)이 있는 그래프, (u, u)
- Multi-Graph: Multi Edge를 가진 그래프 (두 노드 사이 복수의 간선), (u, v) & (u, v)
- 복잡도에 따른 분류
- 희소 그래프 (Sparse Graph)
- 밀집 그래프 (Dense Graph)
- 완전 그래프 (Complete Graph)
희소 그래프
- 각 Vertex들이 상수 개의 Vertex와 연결된 그래프
- 한 Vertex에서 연결된 Vertex의 수: O(1)
- Edge의 수: O(n)
밀집 그래프
- n개의 Vertex들의 대부분이 서로 연결된 그래프
- Edge의 수: O(n²)
- 방향 그래프의 경우에도 O(n²)개의 Edge를 가짐
완전 그래프
- n개의 Vertex들이 서로 연결된 그래프
- 하나의 Vertex가 (n-1)개의 Vertex와 연결됨
- Edge의 수: n(n-1)/2
- 방향 그래프의 경우 n(n-1)개의 Edge를 가짐
그래프의 응용 체계
깊이 우선 탐색넓이 우선 탐색연결 성분신장 트리이중 연결 성분강한 연결 성분최단 경로
- 깊이 우선 탐색 (DFS, Depth-First Search)
- 그래프의 모든 Vertex를 방문할 수 있는 최대한 멀리 방문하는 방식
- 넓이 우선 탐색 (BFS, Breadth-First Search)
- 그래프의 모든 Vertex를 최대한 가까운 Vertex부터 방문하는 방식
- 연결 성분 (Connected Component)
- 서로 방문할 수 있는 Vertex들의 최대 집합을 표시하는 방법
- 신장 트리 (Spanning Tree)
- (n-1)개의 Edge를 n개의 Vertex로 연결하는 부분 그래프
- 이중 연결 성분 (Biconnected Component)
- 한 Vertex와 그 연결 Edge를 모두 제거해도 연결 상태를 유지하는 연결 성분
- 강한 연결 성분 (Strongly Connected Component)
- 방향 그래프에서 서로 방문할 수 있는 Vertex들의 연결 성분
- 최단 경로 (Shortest Path)
- 한 Vertex에서 다른 Vertex로 가는 여러 경로 중에서 그 가중치가 가장 작은 경로
그래프의 이해
- 인접(Adjacent): Vertex u와 v가 Edge로 연결되어 있다면 (u, v) ∈ E (u와 v는 인접해 있음)
- 부속(Incident): 두 Edge가 같은 Vertex를 공유하고 있음 (e.g. (0, 1)과 (0, 2)는 부속)
- 부분 그래프(Subgraph): G = (V, E), G′ = (V′, E′)일 때 V′⊆V, E′⊆E이면 G′은 G의 부분 그래프
- 경로(Path): Vertex u에서 Vertex v로 가는 경로는 다음을 만족하는 Vertex들의 연속체
- (u, i₁), (i₁, i₂), ..., (iₖ, v) ∈ E
- Path (u, v) = (u, i₁, i₂, ..., iₖ, v)
- 경로의 길이: 경로에 있는 Vertex 또는 Edge의 수, 가중치 그래프의 경우 경로 상 Edge들의 가중치의 합
- 최단 경로: 여러 경로 중에서 그 길이가 최소인 경로
- 단순 경로: 시작과 끝을 제외한 모든 Vertex가 서로 다른 경로
- 순환(Cycle): 한 Vertex에서 시작해서 다시 자기 자신으로 돌아오는 경로
- 비순환 그래프(Acyclic Graph): 순환이 존재하지 않는 그래프
- 연결: 두 Vertex 사이에 경로가 존재하는 상태
- 연결 그래프: 그래프에 속한 모든 쌍의 Vertex들이 연결된 그래프
- 연결 성분: 연결된 부분 그래프의 최대치
- 방향 그래프에서는 경로에 방향성이 추가되기 때문에 강한 연결이라고 함
- 강한 연결 성분: 강하게 연결된 부분 그래프의 최대치
- 차수(Degree): Vertex에 연결된 Edge의 수
- 신장트리(Spanning Tree)
- 그래프 G = (V, E)의 부분 그래프 T = (V', E')
- 조건 ①: V' = V, E' ⊆ E, |E'| = |V| - 1
- 조건 ②: E'은 순환이 없음
- T = (V', E')가 위 두 조건을 만족시킬 때 T는 G의 신장트리
그래프의 구현
- 인접 행렬(Adjacency Matrix): 그래프의 모든 Vertex들 간에 존재하는 Edge를 행렬의 형태로 표현하는 방식
- 인접 리스트(Adjacency List): 그래프의 모든 Vertex들 간에 존재하는 Edge를 연결 리스트의 형태로 표현하는 방식
- 성능 비교
| 인접 행렬 | 인접 리스트 | |
| 완전 or 밀집 그래프 | O(n²) | O(n²) |
| 희소 그래프 | O(n²) | O(n) |
인접 리스트를 이용한 그래프 구현
- 입력 그래프: Indexed Edge List 방식으로 표현된 그래프를 입력
Input: // undirected graph
4 5 // 4: # of vertices (1 ~ 4)
1 2 // 5: # of edges
1 3
1 4
2 4
3 4- 그래프 입력 함수
nptr edge[10001];
void main()
{
scanf("%d %d %d", &n, &m, &s);
for (i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
edge[u].add(v);
edge[v].add(u);
}
for (i = 1; i <= n; i++)
edge[i].sort();
}그래프의 개념
그래프의 유래
- 쾨니히스베르크(Konigsberg) 다리 문제
- 오일러가 그래프 개념을 도입해서 해결
- 땅과 섬 → Node (Vertex)
- 다리 → Edge (Link)
- 다리 문제 → 한 붓 그리기
- 한 붓 그리기 문제
- 홀수 개의 Edge에 연결된 Vertex의 수가 4개 이상이면 한 붓 그리기가 불가능한 도형
그래프의 정의
- 개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델
- Vertex: 꼭짓점, 정점, 노드
- Vertex는 대체를 나타냄
- Edge: 간선
- 1:1 관계, 노드의 쌍으로 표현
그래프의 표현
- 그래프를 Vertex와 Edge의 쌍으로 표현
- G = (V, E)
- 수학적 표현
- Vertex: 모든 Vertex들의 집합, V = {0, 1, 2, 3}
- Edge: Vertex 쌍들의 집합, E = {(0, 2), (0, 3), (1, 2), (1, 3)}
- 시각적 표현
- Vertex: 원과 원 내부의 기호로 표현
- Edge: Vertex와 Vertex를 연결하는 실선으로 표현
- Edge List를 이용한 표현
- 코딩 테스트에서 가장 많이 사용하는 표현
4, 4 // ─ Vertex의 수와 Edge의 수
0, 2 // ┌ 각 줄 마다
0, 3 // │ Edge를
1, 2 // │ 나타냄
1, 3 // └ (Vertex의 쌍)그래프의 종류
- 방향과 가중치에 따른 분류
- 무방향 그래프 (Graph)
- 방향 그래프 (Directed Graph)
- 가중치 그래프 (Weighted Graph)
- 방향 가중치 그래프 (Weighted Directed Graph)
- 특별한 그래프
- Self-Graph: 순환(자기 자신으로의 Edge)이 있는 그래프, (u, u)
- Multi-Graph: Multi Edge를 가진 그래프 (두 노드 사이 복수의 간선), (u, v) & (u, v)
- 복잡도에 따른 분류
- 희소 그래프 (Sparse Graph)
- 밀집 그래프 (Dense Graph)
- 완전 그래프 (Complete Graph)
희소 그래프
- 각 Vertex들이 상수 개의 Vertex와 연결된 그래프
- 한 Vertex에서 연결된 Vertex의 수: O(1)
- Edge의 수: O(n)
밀집 그래프
- n개의 Vertex들의 대부분이 서로 연결된 그래프
- Edge의 수: O(n²)
- 방향 그래프의 경우에도 O(n²)개의 Edge를 가짐
완전 그래프
- n개의 Vertex들이 서로 연결된 그래프
- 하나의 Vertex가 (n-1)개의 Vertex와 연결됨
- Edge의 수: n(n-1)/2
- 방향 그래프의 경우 n(n-1)개의 Edge를 가짐
그래프의 응용 체계
깊이 우선 탐색넓이 우선 탐색연결 성분신장 트리이중 연결 성분강한 연결 성분최단 경로
- 깊이 우선 탐색 (DFS, Depth-First Search)
- 그래프의 모든 Vertex를 방문할 수 있는 최대한 멀리 방문하는 방식
- 넓이 우선 탐색 (BFS, Breadth-First Search)
- 그래프의 모든 Vertex를 최대한 가까운 Vertex부터 방문하는 방식
- 연결 성분 (Connected Component)
- 서로 방문할 수 있는 Vertex들의 최대 집합을 표시하는 방법
- 신장 트리 (Spanning Tree)
- (n-1)개의 Edge를 n개의 Vertex로 연결하는 부분 그래프
- 이중 연결 성분 (Biconnected Component)
- 한 Vertex와 그 연결 Edge를 모두 제거해도 연결 상태를 유지하는 연결 성분
- 강한 연결 성분 (Strongly Connected Component)
- 방향 그래프에서 서로 방문할 수 있는 Vertex들의 연결 성분
- 최단 경로 (Shortest Path)
- 한 Vertex에서 다른 Vertex로 가는 여러 경로 중에서 그 가중치가 가장 작은 경로
그래프의 이해
- 인접(Adjacent): Vertex u와 v가 Edge로 연결되어 있다면 (u, v) ∈ E (u와 v는 인접해 있음)
- 부속(Incident): 두 Edge가 같은 Vertex를 공유하고 있음 (e.g. (0, 1)과 (0, 2)는 부속)
- 부분 그래프(Subgraph): G = (V, E), G′ = (V′, E′)일 때 V′⊆V, E′⊆E이면 G′은 G의 부분 그래프
- 경로(Path): Vertex u에서 Vertex v로 가는 경로는 다음을 만족하는 Vertex들의 연속체
- (u, i₁), (i₁, i₂), ..., (iₖ, v) ∈ E
- Path (u, v) = (u, i₁, i₂, ..., iₖ, v)
- 경로의 길이: 경로에 있는 Vertex 또는 Edge의 수, 가중치 그래프의 경우 경로 상 Edge들의 가중치의 합
- 최단 경로: 여러 경로 중에서 그 길이가 최소인 경로
- 단순 경로: 시작과 끝을 제외한 모든 Vertex가 서로 다른 경로
- 순환(Cycle): 한 Vertex에서 시작해서 다시 자기 자신으로 돌아오는 경로
- 비순환 그래프(Acyclic Graph): 순환이 존재하지 않는 그래프
- 연결: 두 Vertex 사이에 경로가 존재하는 상태
- 연결 그래프: 그래프에 속한 모든 쌍의 Vertex들이 연결된 그래프
- 연결 성분: 연결된 부분 그래프의 최대치
- 방향 그래프에서는 경로에 방향성이 추가되기 때문에 강한 연결이라고 함
- 강한 연결 성분: 강하게 연결된 부분 그래프의 최대치
- 차수(Degree): Vertex에 연결된 Edge의 수
- 신장트리(Spanning Tree)
- 그래프 G = (V, E)의 부분 그래프 T = (V', E')
- 조건 ①: V' = V, E' ⊆ E, |E'| = |V| - 1
- 조건 ②: E'은 순환이 없음
- T = (V', E')가 위 두 조건을 만족시킬 때 T는 G의 신장트리
그래프의 구현
- 인접 행렬(Adjacency Matrix): 그래프의 모든 Vertex들 간에 존재하는 Edge를 행렬의 형태로 표현하는 방식
- 인접 리스트(Adjacency List): 그래프의 모든 Vertex들 간에 존재하는 Edge를 연결 리스트의 형태로 표현하는 방식
- 성능 비교
| 인접 행렬 | 인접 리스트 | |
| 완전 or 밀집 그래프 | O(n²) | O(n²) |
| 희소 그래프 | O(n²) | O(n) |
인접 리스트를 이용한 그래프 구현
- 입력 그래프: Indexed Edge List 방식으로 표현된 그래프를 입력
Input: // undirected graph
4 5 // 4: # of vertices (1 ~ 4)
1 2 // 5: # of edges
1 3
1 4
2 4
3 4- 그래프 입력 함수
nptr edge[10001];
void main()
{
scanf("%d %d %d", &n, &m, &s);
for (i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
edge[u].add(v);
edge[v].add(u);
}
for (i = 1; i <= n; i++)
edge[i].sort();
}