[알고리즘/C++] 그래프 순회 - 깊이 우선 탐색(DFS)

그래프는 정보 간의 연결 관계를 나타내기 위한 자료 구조이다. 

 

search나 중복값 탐색을 위해 그래프 전체를 순회해야할 경우가 생기는데 

 

그래프 순회를 위한 기법 중 하나가 깊이 우선 탐색(Depth first search, DFS)이다. 

 

그래프를 나타내기 위해 많이 사용하는 방법 중 하나가 인접 리스트이다. 

 

void initGraph2(vector<vector<pair<int,int>>>& adj) {
	adj.push_back({ {0, 0} });
	//sentinel node
	adj.push_back({ {2, 5}, {4, 9}, {5, 1} });
	adj.push_back({ {1, 5}, {3, 2} });
	adj.push_back({ {2, 2}, {4, 6} });
	adj.push_back({ {1, 9}, {3, 6}, {5, 2} });
	adj.push_back({ {1, 1}, {4, 2} });
}

 

위는 C++의 Vector와 Pair 자료구조를 이용해 그래프의 인접 리스트를 표현한 것이다. 

 

가장 먼저 구현의 편의를 위해 보초값(sentinel value)를 넣어주고 아래부터 차례로 

 

node1, node2 .... node5의 {이웃 노드, 가중치} 값의 리스트를 나타낸다. 

 

위와 같은 형태로 그래프가 구성된다. 

 

 

깊이 우선 탐색은 노드를 따라 가장 말단의 노드(Leaf node)까지 도달한 뒤에 다시 호출한 노드로 돌아가서 

 

다시 탐색하지 못한 다른 Leaf 노드까지 순회하되 전체 노드를 한번씩만 방문하여 순회하는 방식이다. 

 

void dfs(vector<vector<pair<int, int>>> adj, vector<bool>& visited, int cur) {
	if (visited[cur]) {
		return;
	}
	visited[cur] = true;
	cout << cur << "\n";
	for (int i = 0; i < adj[cur].size(); i++) {
		dfs(adj, visited, adj[cur][i].first);
	}
}

dfs를 구현하기 위해 필요한 배열(벡터)이 visited이다. 

 

각 노드는 한번씩만 방문되어야 하기 때문에 해당 노드를 방문했다면 함수를 반환하고, 

 

첫 방문이라면 방문 기록을 남겨둔다. 

 

그리고 나서 현재 노드의 가장 첫번째 자식 노드를 따라서 dfs 함수를 재귀호출한다.

void initTree(vector<vector<pair<int, int>>>& adj) {
	adj.push_back({ {0, 0} });
	//sentinel node
	adj.push_back({ {2, 1}, {3, 1}, {4, 1} });
	adj.push_back({ {5, 1}, {6, 1} });
	adj.push_back({ {7, 1} });
	adj.push_back({ {8, 1}, {9, 1} });
	adj.push_back({ { 10, 1 }, { 11, 1 } });
	adj.push_back({}); //node6 ~ node11은 leaf node
	adj.push_back({});
	adj.push_back({});
	adj.push_back({});
	adj.push_back({});
	adj.push_back({});
}

dfs의 특성을 더 잘 알아보기 위해 트리 형태로 초기화하였다.

	vector<vector<pair<int, int>>> adj;
	initTree(adj);
	vector<bool> visited(adj.size(), false);
	dfs(adj, visited, 1);

아래는 결과이다.

1
2
5
10
11
6
3
7
4
8
9