📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.
그래프
그래프 G(V, E)
V(Vertex, 정점)
E(Edge, 간선)
그래프의 표현 방법
인접 리스트 표현
- 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프를 표현
- 각 정점마다 하나의 연결 리스트를 가짐
vector<list<int>> adjacent;
vector<list<pair<int, int>>> adjacent; // 가중치 그래프adjacent[i] : 정점 i와 간선을 통해 연결된 정점들의 번호를 저장하는 연결 리스트
- 두 정점이 주어질 때 연결되어있는지 알기 위해서는 연결 리스트를 일일이 뒤져야 함
인접 행렬 표현
- V x V 크기의 행렬, 2차원 배열을 이용해 그래프의 간선 정보 저장
vector<vector<bool>> adjacent;
vector<vector<int>> adjacent; // 가중치 그래프adjacent[i, j] : 정점 i에서 정점 j로 가는 간선이 있는지를 나타내는 불린 값 변수
- 두 정점이 주어질 때 한 번의 배열 접근만으로 두 정점을 잇는 간선이 있는지 확임 가능
- 실제 간선의 개수와 관계 없이 항상 O(V^2) 크기의 공간 사용
깊이 우선 탐색(DFS, Depth-First Search)
그래프의 모든 정점을 발견하는 방법
현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라감. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아감 -> 재귀 호출
vector<vector<int>> adj; // 그래프의 인접 리스트
vector<bool> visited; // 각 정점을 방문했는지 - visited[0] == true이면 0번 정점은 방문했음
void dfs(int here) {
cout << "DFS visits " << here << "\n";
visited[here] = true;
for(int i = 0; i < adj[here].size(); ++i){
int there = adj[here][i];
if(!visited[there) // 아직 방문하지 않은 경우 방문
dfs(there);
}
}
void dfsAll() {
visited = vector<bool> (adj.size(), false);
for(int i = 0; i < adj.size(); ++i)
if(!visited[i]) dfs(i);
}dfs() : 현재 정점과 인접한 정점을 순차적으로 방문
dfsAll() : 그래프가 하나의 컴포넌트로 이루어지지 않은 경우에도 모든 정점 방문
두 정점이 서로 연결되어 있는가 확인
dfs(u) 를 수행하면 u에서부터 간선들을 통해 갈 수 있는 모든 정점을 방문
-> visited[] 를 참조하면 u에서 갈 수 있는지 확인 가능(true인 경우 연결되어 있음)
연결된 부분집합의 개수 세기
dfs() 함수는 시작한 정점에서 갈 수 있는 모든 정점을 방문 -> 같은 컴포넌트에 속한 점은 모조리 방문
-> dfsAll()에서 dfs()의 호출 횟수를 세면 그래프가 몇 개의 컴포넌트로 나뉘어 있는지 확인 가능
위상 정렬
의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산
의존성 그래프
- 각 작업을 정점으로 표현, 작업 간의 의존 관계를 간선으로 표현한 방향 그래프
- 사이클이 없는 방향 그래프(DAG)
모든 의존성이 만족되려면, 모든 간선이 왼쪽에서 오른쪽으로 가야함
이러한 DAG의 정점을 배열하는 문제를 위상 정렬이라고 함
구하는 방법
dfsAll()을 수행하며dfs()가 종료할 때마다 현재 정점의 번호를 기록dfsAll()이 종료한 뒤 기록된 순서를 뒤집음- 결과가 1-2-3인데 실제 순서에서 3-1이 가능한 경우 사이클이 생겨 위상 정렬 불가
오일러 서킷(Eulerian Circuit)
그래프의 모든 간선을 정확히 한 번씩 시자나서 시작점으로 돌아오는 경로 찾기
무방향 그래프에서 오일러 서킷이 존재하기 위한 조건
- 모든 정점이 짝수점(정점의 차수가 짝수)
❔ 방향 그래프에서는 나가는 각 정점에서 들어오는 간선의 수와 나가는 간선의 수가 같아야 함- 간선들이 하나의 컴포넌트에 포함
// adj[i][j] : i와 j 사이의 간선의 수
vector<vector<int>> adj;
void getEulerCircuit(int here, vector<int>& circuit) {
for(int there = 0; there < adj.size() ; ++there) {
while(adj[here][there] > 0) {
adj[here][there]--; // 양쪽 간선을 모두 지움
adj[there][here]--;
getEulerCircuit(there, circuit);
}
}
curcuit.push_back(here);
}📍 오일러 트레일(시작점과 끝점이 다른 경우) 구하기
점 a에서 시작해서 b에서 끝나는 오일러 트레일을 찾는 경우, a와 b 사이에 간선 (b, a)를 추가한 뒤 오일러 서킷을 찾고 (b, a) 간선을 지워 서킷을 끊으면 됨
간선 구분
트리 간선 : 스패닝 트리에 포함된 간선
순방향 간선 : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선
역방향 간선 : 스패닝 트리의 자손에서 선조로 연견되는 간선
교차 간선 : 그 외 나머지 간선
- (u, v)가 순방향 간선인 경우 - v는 u의 자손, 즉 v는 u보다 늦게 발견
- (u, v)가 역방향 간선인 경우 - v는 u의 선조, 즉 v는 u보다 일찍 발견
- (u, v)가 교차 간선인 경우 - dfs(v)가 종료한 후 dfs(u)가 호출, 즉 v는 u보다 일찍 발견
✔️ 간선 구분을 위해서는 발견 순서 정보를 저장해야함
vector<vector<int>> adj;
// discovered[i] : i번 정점의 발견 순서
// finished[i] : dfs(i)가 종료했으면 1, 아니면 0
vector<int> discovered, finished;
int counter; // 지금까지 발견한 정점의 수
void dfs(int here) {
discovered[here] = counter++;
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i];
// 아직 방문한 적 없다면 방문
if(discovered[there] == -1) {
cout << "tree edge"<< "\n";
dfs(there);
}
// there이 here보다 늦게 발견됐다면 there은 here의 후손
else if(discovered[here] < discovered[there])
cout << "forward edge" << "\n";
// dfs[there]이 아직 끝나지 않았다면 there은 here의 선조
else if(finished[there] == 0)
cout << "back edge" << "\n";
// 나머지 경우는 모두 교차간선
else cout << "cross edge" << "\n";
}
finished[here] = 1;
}