[알고리즘] DFS와 BFS

1. DFS(Depth-First Search)

- 깊이 우선 탐색

- 루트 노드나 임의 노드에서 "다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색"하는 방법

- 스택이나 재귀함수를 이용해 구현

- 모든 경로를 방문해야 할 경우 적합

 

<시간 복잡도>

- 인접 행렬 : O(V^2)

- 인접 리스트 : O(V+E) // V는 접점, E는 간선

 

2. BFS(Breadth-First Search)

- 너비 우선 탐색

- 루트 노드나 임의 노드에서 "인접한 노드부터 먼저 탐색"하는 방법

- 큐를 이용해 구현

- 최소 비용으로 탐색을 진행할 때 적합\

 

<시간 복잡도>

- 인접 행렬 : O(V^2)

- 인접 리스트 : O(V+E)

 

3. 소스코드(C++)

// DFS
#include <iostream>
#include <vector>

using namespace std;

int map[1001][1001];
int dfs[1001];

void init(int*, int);
void DFS(int, int);

int main()																 
{
	init(*map, sizeof(map) / 4);
	init(dfs, sizeof(dfs) / 4);

	// 노드 개수, 간선 개수, 시작 노드
	int NodeNum, EdgeNum, StartNode; 
	cin >> NodeNum >> EdgeNum >> StartNode;
	
	// 모든 간선들의 정보를 입력, 저장
	for (int i = 0; i < EdgeNum; i++)
	{		
		int start, end;
		cin >> start >> end;

		map[start][end] = 1;
		map[end][start] = 1;
	}
	
	cout << "--------------------------------------" << endl;

	// 깊이 우선 탐색 시작
	DFS(StartNode, NodeNum);

	return 0;
}

void init(int* arr, int size)
{
	// 배열 초기화
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

void DFS(int curNode, int childNodeNum) // 현재 노드, 자식 노드 갯수
{
	dfs[curNode] = 1; // 현재 노드의 사용을 표시
	cout << curNode << " "; // 현재 탐색한 노드를 출력

	// 자신의 자식 노드를 탐색
	for (int i = 1; i <= childNodeNum; i++)
	{
		if (map[curNode][i] == 1 && dfs[i] == 0)
		{
			DFS(i, childNodeNum);
		}
	}
}

// BFS
#include <iostream>

using namespace std;

int map[1001][1001];
int bfs[1001];
int queue[1001];

void init(int*, int);
void BFS(int, int);

int main()																 
{
	init(*map, sizeof(map) / 4);
	init(bfs, sizeof(bfs) / 4);
	init(queue, sizeof(queue) / 4);

	// 노드 개수, 간선 개수, 시작 노드
	int NodeNum, EdgeNum, StartNode; 
	cin >> NodeNum >> EdgeNum >> StartNode;

	// 모든 간선들의 정보를 입력, 저장
	for (int i = 0; i < EdgeNum; i++)
	{
		int start, end;
		cin >> start >> end;

		map[start][end] = 1;
		map[end][start] = 1;
	}

	cout << "--------------------------------------" << endl;

	// 너비 우선 탐색 시작
	BFS(StartNode, NodeNum);

	return 0;
}

void init(int* arr, int size)
{
	// 배열 초기화
	for (int i = 0; i < size; i++)
	{
		arr[i] = 0;
	}
}

void BFS(int v, int N)
{
	int front = 0;
	int rear = 0;
	int pop;
	
	cout << v << " "; // 현재 노드 출력

	queue[rear++] = v; // 큐에 현재 노드 저장
	bfs[v] = 1; // 현재 노드를 탐색했음을 표시

	while (front < rear)
	{
		pop = queue[front++]; // 현재 노드

		// 현재 노드와 직접 연결된 노드들을 먼저 탐색
		for (int i = 0; i <= N; i++)
		{
			// 현재 노드와 연결되어 있고, 아직 탐색하지 않은 경우
			if (map[pop][i] == 1 && bfs[i] == 0)
			{
				cout << i << " "; // 연결되어있는 노드 출력
				queue[rear++] = i; // 큐에 연결노드 저장 -> 다음 반복에 사용
				bfs[i] = 1; // 탐색했음을 표시
			}
		}
	}
}

 

4. 코드 실행 예시

- 아래와 같은 구조를 예시로 사용하였다.

1) DFS(깊이 우선 탐색)

2) BFS(너비 우선 탐색)

DFS의 경우 깊이우선탐색이므로 1->2->5->3->