깊이 우선 탐색(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 = vector<bool>(adj.size(), false);

	for (int i = 0; i < adj.size(); i++)
		if (!visited[i])
			dfs(i);
}

위상 정렬

**의존성 그래프 (dependency graph)**는 의존성이 있는 정점이 주어졌을 때, 이 의존 관계를 간선으로 표현한 방향 그래프이다. 간선 (u, v) 는 v 정점이 u 정점에 의존하고 있음을 보여준다.

이 그래프는 사이클 없는 방향 그래프, 즉 DAG (Directed Acyclic Graph)임을 의미한다. 이 DAG의 정점을 배열하는 문제를 **위상 정렬 (topological sort)**라고 한다. 위상 정렬에서는 모든 간선 (u, v)에 대하여 정점 u와 정점 v가 먼저 오는 순서로 정렬해야 한다.

Untitled

이 위상 정렬을 코드로 구현해보자.

그래프를 따라 정점을 지나고, 다음 정점을 재귀호출한 뒤 호출이 끝나는 경로를 따라 order 에 정점의 번호를 기록한다. 그리고 order 배열을 뒤집으면 위상 정렬 결과를 얻을 수 있다.

고대어 사전(DICTIONARY)

여기서는 주어진 입력은 사전 상에서 인접하다는 특징이 있다. 따라서 인접한 정점만 검사해서 사전에 알파벳을 기록하더라도 모든 정점을 검사한 것과 같은 효과를 볼 수 있다.

// adj[i][j]는 알파벳 i가 j보다 앞에 와야 함을 나타낸다.
// 주어진 입력을부터 알파벳의 선후 관계를 생성한다. 
void makeGraph(const vector<string>& words) {
	adj = vector<vector<int>>(26, vector<int>(26, 0));
	for (int j = 1; j < words.size(); j++) {
		int i = j - 1; 
		int len = min(words[i].size(), words[j].size());

		for (int k = 0; k < len; k++) {
			if (words[i][k] != words[j][k]) { // 주어진 인접한 문자열에서 동일하지 않은 문를 찾는다.
				int a = words[i][k] - 'a';
				int b = words[j][k] - 'a';
				adj[a][b] = 1; // a가 b보다 앞선다. 
				break;
			}
		}
	}
}

vector<int> seen, order;
void dfs(int here) {
	seen[here] = 1;
	for (int there = 0; there < adj.size(); there++)
		if (!seen[there] && adj[here][there])
			dfs(there);
	order.push_back(here);
}

// adj에 주어진 그래프를 위상 정렬한다.
// 위상 정렬할 수 없다면 (DAG가 아니라면) 빈 벡터를 반환한다.
vector<int> topologicalSort() {
	int n = adj.size();
	seen = vector<int>(n, 0);
	order.clear(); 
	for (int i = 0; i < n; i++) if (!seen[i]) dfs(i);
	reverse(order.begin(), order.end());

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (adj[order[j]][order[i]]) // 뒤에서 앞 방향을 가리키는 간선이 있다면
				return vector<int>(); // 빈 벡터를 반환
}

오일러 서킷 (Eulerian circuit)

그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로이다. 오일러 서킷은 아래의 경우에 존재할 수 있다.