[그래프] 그래프의 탐색

서론

이 글에서는 DFS와 BFS에 대해 설명할 것입니다.
DFS는 Depth First Search의 약자이며, 해석하면 깊이 우선 탐색입니다.
BFS는 Breadth First Search의 약자이며, 해것하면 너비 우선 탐색입니다.

DFS

DFS는 한 곳으로 끝까지 파고드는 것을 원칙으로 작동합니다.
계속 파고 들어가다가 이미 방문한 정점을 제외하고는 갈 곳이 없을 경우, 이전 노드로 돌아가서 다른 곳으로 끝까지 파고들어 갑니다.

작동 과정을 조금 상세하게 적어보겠습니다.

시작 정점을 “방문 했음”으로 설정
인접한 정점에서 아직 방문하지 않은 정점을 시작 정점으로 잡은 뒤 1번 다시 실행(재귀 호출)
인접한 정점 중 더 이상 방문하지 않은 정점이 없다면 이전 정점으로 돌아가서 2번 실행
모든 정점 방문 완료시 탐색 종료

코드로 구현을 하면,

int map[1001][1001] = {0}, visit[1001];
//map : 인접 행렬, visit : 방문 체크

void dfs(int v){
	visit[v] = 1;
	printf("%d ", v);
	for(int i=1; i<=n; i++){
		if(map[v][i] == 1 && !visit[i]){
			dfs(i);
		}
	}
}

그래프는 인접 행렬로 표현했습니다.
dfs함수의 매개변수 v는 탐색 시작 노드입니다.
visit[v] = 1; 에서 현재 정점을 “방문 했음”으로 체크합니다.
printf(“%d”, v); 는 DFS탐색 순서를 출력하기 위해 넣었습니다.
for문을 돌림으로써 모든 정점을 순회합니다.
if문에서는 i가 인접한 정점인지, 그리고 방문을 안했는지를 검사합니다.
dfs(i)는 i를 시작 정점으로 잡은 뒤 다시 탐색을 시작하게 하는 재귀 호출 부분입니다.

BFS

BFS는 양 옆을 살피며 탐색 하는 것을 원칙으로 작동합니다.
한 정점에서 갈 수 있는 모든 정점을 순서대로 탐색한 뒤, 다음 단계로 넘어가는 방식으로 탐색을 합니다.

작동 과정을 조금 더 상세하게 적어보겠습니다.

시작 정점을 “방문 했음”으로 설정하고 큐(queue)에 삽입
큐에서 정점 하나를 제거
2에서 제거한 정점과 인접한 정점 중 아직 방문하지 않은 정점을 “방문 했음”으로 설정하고 큐에 삽입
큐가 비어있지 않으면 2로 복귀

코드로 구현을 해봅시다.

int map[1001][1001]={0}, visit1[1001];
int q[1001];
int front=0, rear=0;

void bfs(int v){
	visit1[v] = 1;
	printf("%d ", v);
	q[rear++] = v;
	while(front < rear){
		v = q[front++];
		for(int i=1; i<=n; i++){
			if(map[v][i]==1 && !visit1[i]){
				visit1[i] = 1;
				printf("%d ", i);
				q[rear++] = i;
			}
		}
	}
}

그래프는 인접 행렬로 표현했습니다.
bfs함수의 매개변수 v는 bfs탐색의 시작 정점입니다.
visit1[v] = 1; 로 v 정점을 “방문 했음”으로 표시합니다.
printf를 통해 현재 정점을 출력하고, 그 다음 줄에서 v를 큐에 삽입합니다.
while문은 큐가 비어있지 않으면 계속 실행을 합니다.
v = q[front++]에서 큐에서 삭제한 정점을 v에 저장합니다. for문을 돌림으로써 모든 정점을 순회합니다. if문에서는 i가 인접한 정점인지, 그리고 방문을 안했는지를 검사합니다.
if문 조건을 만족한다면, 그 정점을 “방문 했음”으로 표시하고 출력한 뒤, 큐에 삽입합니다.

서론

DFS

BFS

추천 문제