[알고리즘][그래프의 탐색] 그래프의 깊이 우선 탐색 Part 1

chellchell·2020년 8월 28일

깊이 우선 탐색

알고리즘 이론

목록 보기

10/11

깊이 우선 탐색(Depth - first search, DFS)

더 따라갈 간선이 없을 경우 이전으로 돌아간다
- 재귀호출 사용 - 지금까지 거쳐온 정점들을 모두 저장

인접리스트로 표현된 그래프의 깊이 우선 탐색

#include <iostream>
#include <vector>
using namespace std;
//그래프의 인접 리스트 표현
vector<vector<int>>adj;
//각 정점을 방문했는지 여부
vector<bool>visited;
//깊이 우선 탐색
void dfs(int here) {
	cout << "DFS visits " << here << endl;
	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를 모두 false로 초기화한다.
	visited = vector<bool>(adj.size(), false);
	//모든 정점을 순회하면서, 아직 방문한 적 없으면 방문한다.
	for (int i = 0; i < adj.size(); i++) {
		if (!visited[i])
			dfs(i);
	}
}

dfs() : 아직 방문하지 않은 정점으로 이어지는 간선을 만날경우 재귀호출을 통해 해당 정점 방문
dfsAll() : 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에 dfs()만으로는 모든 정점을 순서대로 발견하지 못할 수 있음.

깊이 우선 탐색 사용 예

두 정점이 서로 연결되어 있는가 확인

어떤 정점 u에 대해 dfs(u)를 수행하면, u에서부터 간선들을 통해 갈 수 있는 모든 정점 방문
dfs(u)수행 후 visited[]를 참조하면 u로부터 각 정점에 갈 수 있는지 확인 가능

연결된 부분집합의 개수 세기

component/요소: 무향 그래프가 간선으로 서로 연결되지 않은 몇 개의 조각으로 쪼개져 있는 경우
dfsAll()에서 dfs()를 호출하는 횟수를 세면 몇 개의 컴포넌트로 나뉘어 있는지 확인 가능

위상 정렬

의존성이 있는 작업들이 주어질 때, 어떤 순서롤 수행해야 하는지 계산
작업 B를 하기 전에 반드시 작업 A를 해야 한다 ⇔ 작업 B가 작업 A에 의존한다

-의존성 그래프

정점 : 작업 , 간선 : 작업 간의 의존관계 으로 표현한 방향 그래프
사이클이 없는 방향 그래프 (DAG)

-위상 정렬

그래프의 정점들을 일렬로 늘어놓고, 왼쪽에서부터 하나씩 수행하도록 정점들을 배열
DAG의 정점들을 배열
dfsAll()을 수행하면 dfs()가 종료할 때마다 현재 정점의 번호 기록
dfsAll() 종료 후 기록된 순서 뒤집기
- dfs()가 늦게 종료한 정점일수록 정렬 결과의 앞에 옴

오일러 서킷

오일러 서킷(Eulerian circuit) : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제

-오일러 서킷의 존재 조건

그래프의 모든 정점들이 짝수점(차수가 짝수인 정점) 이어야함
하나의 컴포넌트에 포함된 그래프

구현

#include <iostream>
#include <vector>
using namespace std;
//그래프의 인접 행렬 표현. adj[i][j]=i와 j사이의 간선의 수
vector<vector<int>> adj;
//무향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷 계산
//결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다
void getEulerCircuit(int here, vector<int>& circuit) {
	for (int there = 0; there < adj[here].size(); there++) {
		while (adj[here][there] > 0) {
			adj[here][there]--;
			adj[there][here]--;
			getEulerCircuit(there, circuit);
		}
	}
	//재귀호출이 끝나고 반환 할 때 추가
	circuit.push_back(here);
	//경로의 끝점부터 역순으로 간선들이 추가
}