[알고리즘 - 이론] 그래프의 탐색 (DFS, BFS)

한 정점에서 시작하여 연결된 모든 정점을 한번씩 방문하는 방법

1. DFS (깊이 우선 탐색)

• 재귀 호출을 이용한 구현

void dfs(int x){
	check[x] = true;
    for (int i = 0; i <a[x].size(); i++){
    	int y = a[x][i];
    	if (check[i] == false) {
        	dfs(y);
        }
    }
} 
O(V^2)[인접행렬] -> O(V+E) [인접리스트] 으로 단축!

---

2. BFS (너비 우선 탐색)

• queue를 이용한 구현

queue<int> q;
check[1] = true;
q.push(1);
while(!q.empty) {
	int x = q.front(); q.pop();
    for (int i = 0; i < a[x].size(); i++){
    	int y = a[x][i];
    	if (check[y] == false) {
        	check[y] = true; q.push(y);
        }
}

---

3. DFS 과 BFS

bool check[1001];
vector<int> a[1001];

void dfs(int node) {
	check[node] = true;
	cout << node << " ";
	for (int i = 0; i < a[node].size(); i++) {
		int next = a[node][i];
		if (check[next] == false) {
			dfs(next);
		}
	}
}

void bfs(int start) {
	queue<int> q;
	memset(check, false, sizeof(check));
	check[start] = true;
	q.push(start);
	while (!q.empty()) {
		int node = q.front(); q.pop();
		cout << node << " ";
		for (int i = 0; i < a[node].size(); i++) {
			int next = a[node][i];
			if (check[next] == false) {
				check[next] = true;
				q.push(next);
			}
		}
	}
}

int main() {
	int n, m, start;
	cin >> n >> m >> start;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		sort(a[i].begin(), a[i].end()); //a[i] inner sorting
	}
	dfs(start);
	cout << "\n";
	bfs(start);
	cout << "\n";
	return 0;
}

---

4. 기억할 점

• Vector 내를 정렬하고 싶은 경우
  : sort(a[i].begin(), a[i].end())

• 배열을 초기화 하고 싶은 경우
  : memset(check, false, sizeof(check))