안농하세요~~ 다시 힘찬 월요일~~
내용 중 잘못된 부분이 있다면 알려주세요!
그래프 챕터 진도가 끝난게 아니라 우선 오늘 한 내용까지만 정리정리~
Chap 5. 그래프
- summary
1. 오일러 사이클
- 오일러 사이클?
: 각 정점과 간선을 한번씩만 사용하여 제자리로 돌아올 수 있는 사이클
그래프 G가 오일러 사이클은 가진다 = 그래프 G는 연결되어있고, 각 정점은 짝수 차수이다
단) 홀수 차수의 점이 2개 존재하면, 돌아오는건 안되지만 한붓그리기까지는 가능
2. 그래프
- 용어
- 무향 간선 : 방향이 존재하지 않는 간선
- 유향 간선
- 인접 : 당사자 정점을 연결하는 직접적인 간선이 존재함. '정점 v1와 v2는 인접한다'
- 부속 : 주로 무향간선에 대해 사용하는 용어. '간선 e는 정점 v1,v2에 부속한다'
- 차수 : 정점에 부속된 간선의 개수. indegree & outdegree (유향간선에 대해)
- 다중 간선
- self-loop : 방향성 있을때 사용
- 경로 : 정점과 간선이 교대로 구성된 sequence. 예) Path(A,B)=[A,q,B]
- 단순경로 : 정점과 간선이 중복되지 않는 경로
- 회로 : 시작 정점과 끝 정점이 같은 경로
- 단순 회로 : 정점과 간선이 중복되지 않는 회로
- 연결됨 : 정점 v1으로부터 정점 v2까지로의 경로가 존재하면 연결되어 있다. != 인접
- 그래프 종류
- 무향 그래프
- 유향 그래프
- 가중치 그래프 : 가중치/비용을 갖는 간선으로 이뤄짐 (때때로 정점)
- 정규 그래프 : 모든 정점이 동일한 차수 가짐
- 완전 그래프 : 임의의 두 정점에 대해 그를 잇는 간선 존재. 무향그래프의 간선 갯수 : N(N-1)/2개 | 유향 ~ : N(N-1)개
- 연결 그래프 : 임의의 두 정점에 대한 경로 존재
- 부분 그래프
- 트리 그래프 : 순환을 갖지 않는 연결 그래프. 임의의 두 정점에 대해서 경로가 오직 한개만 존재. 한개 이상의 정점 가짐. 임의의 간선을 제거한 순간 연결 그래프 조건 미충족됨
- 희소 그래프 : 정점 수 >> 간선 수. 대부분 문제들은 희소그래프의 상황 (완전그래프 상황의 간선 수와 비교하는것. ex, 정점 10000개면 완전그래프 간선 수는 10000C2개=5천만개. 따라서 간선 수가 3만개면 희소그래프라 볼 수 있음)
- 그래프 표현
- 간선 리스트 Edge List : 이차원 배열에 간선 정보 저장. 용량이 작은편. 벨만-포드 알고리즘에서 사용
- 인접 행렬 Adjacency Matrix : 행렬에 간선 존재 유무 표시 (0,1로) n=10000일때 저장공간 1억 -> 용량 비효율 (n=1000까지는 대략 사용 가능하긴함) 파악이 쉽다는 장점
- 인접 리스트 Adjacency List : '인접'한 노드만 기록. 검색&메모리의 효율성. 무향그래프는 각 노드에 모두 표시
- 서로소 집합 Disjoint Set, Union-Find
1. Union 연산
void join(int a, int b) {
aroot = find(a);
broot = find(b);
arr[aroot] = broot; //arr는 미리 세팅된 서로소 집합
return;
}
//for (int i = 0; i <= n; i++) {
// arr[i] = i;
//}
2. Find 연산 (재귀로 경로 압축 필수! 안하면 시간복잡도 에바! 경로압축시 시간복잡도: 준 상수 시간)
int find(int a) {
if (arr[a] == a) return a;
else return arr[a] = find(arr[a]);
}
3. DAG (Directed Acyclic Graph)
- 개념
- 순환을 가지지 않는 방향 그래프
- 일반적으로, 우선순위를 가진 일련의 작업들은 DAG 구조를 가짐
- 선행자 & 후행자 : 선행자 -> 후행자
- 즉각 선행자 & 즉각 후행자 : 직접적인 간선 존재시
- 그래프의 '위상'을 나타낼 수 있음
- 즉, 위상 정렬 가능
- 위상정렬 Topological Sort
- DAG에서 그래프의 방향성을 거스르지 않고 정점을 나열하는것
- 각 정점을 우선순위에 따라 배치
- 일반적으로, 위상정렬의 결과는 유일하지 않음
- Indegree 배열 + indegree==0용 큐 + 그래프 인접리스트(vector)로 구현 (Union, Find)
4. 트리
- 정의
- 무향 그래프
- 순환 없음 (따라서 어떠한 두 정점에 대한 단순경로는 오직 한개 존재)
- 연결 그래프
- 특징
- 정점 갯수 - 1 = 간선 갯수
- 기존 트리에 간선 추가할 시, 추가한 간선을 중심으로 사이클 형성됨
- 기존 트리에서 간선 제거할 시, 트리 조건 미충족됨
- 신장 트리 ? 무향 연결 그래프 G의 부분그래프이자, G의 모든 정점을 포함하는 트리 그래프 (걍 주어진 일반적인 그래프에서 만들어낸 트리)
- DST & BST
- 깊이 우선 신장 트리 (DFS Spanning Tree)
- 너비 우선 신장 트리 (BFS Spanning Tree)
- MST 최소 신장 트리
: 무향 연결 가중 그래프 G에서, 간선의 가중치 합이 최소인 신장 트리
* MST 구현 방법
- 크루스칼 Kruskal 알고리즘 : 서로소 집합 (union,find), 구조체(가중치 및 정렬) 등으로 구성
- 프림 Prim 알고리즘 : 우선순위 큐(min heap 최소힙)로 구성