[그래프 탐색] DFS, BFS 정리 (with C++)

DFS(Depth-First Search) : 깊이 우선 탐색

특징

• 모든 노드를 방문
• 재귀함수 or 스택으로 구현

동작 과정

출처 : 위키피디아(깊이 우선 탐색)

1. 시작 노드 스택에 삽입하고 visited = true 처리
2. 스택 최상단 노드에 인접한 노드 중 아직 visited X 노드가 있다?
있다) visited X 노드를 스택에 넣고 visited = true 처리
없다) 스택 최상단 노드 꺼냄
3. 2번 수행할 수 없을 때까지 반복

언제 사용해야 할까?

• 모든 노드를 다 탐색해야 하는 경우
• 경로의 특징, 지나온 노드에 대한 정보가 필요한 경우

소스코드

#include <iostream>
#include <vector>
using namespace std;

bool visited[9];
vector<int> graph[9];

void dfs(int x) {
	visited[x] = true;//노드 방문 처리
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) {
		int y = graph[x][i];//인접 노드
		if (!visited[y]) dfs(y);//방문x->재귀
	}
}

---

BFS(Breadth-First Search) : 너비 우선 탐색

특징

• 가까운 노드부터 탐색
• 큐 자료구조 이용

동작 과정

출처 : 위키피디아(너비 우선 탐색)

1. 시작 노드 큐에 삽입하고 visited = true 처리
2. 큐에서 노드를 꺼낸 뒤, 인접 노드 중 visited X 노드를 전부 큐에 삽입하고 visited = true 처리
3. 2번 수행할 수 없을 때까지 반복

언제 사용해야 할까?

• 미로 탐색
• 최단 경로
• 탐색 제약 조건이 없는 경우 ex) 가중치

소스코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

bool visited[9];
vector<int> graph[9];

void bfs(int start) {
	queue<int> q;
	q.push(start);//처음 노드 삽입
	visited[start] = true;//방문 처리
	while (!q.empty()) {
		int x = q.front();
		q.pop();//맨 앞 노드 꺼냄
		cout << x << " ";
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i];//인접 노드
			if (!visited[y]) {
               		//방문하지 않은 노드 큐에 삽입
				q.push(y);
				visited[y] = true;//방문 처리
			}
		}
	}
}