Algorithm - BFS, DFS

DFS (Depth First Search) 

깊이 우선 탐색

 

동작방식

구현방식

재귀함수 혹은 스택 으로 구현

 

구현순서 

1. 탐색 시작 노드를 스택에 삽입한뒤 방문(Visited)여부 체크

2. 1번노드에서 인접한 노드중 가장 작은 곳 2번 방문 ->2번노드에서 인접한노드3 방문 ->

인접한노드 4 방문 -> 깊은 노드가 없으므로 1번으로 복귀

3. 1번노드에서 가보지 않은 더 깊은 노드는 5번 5번 노드로 방문

--이후 반복--

 

규칙

1. 가보지 않은 더 깊은 노드가 있다면 숫자가 작은 곳을 우선시하며 방문

2. 더이상 가보지 않은 더 깊은 노드가 있다면 이전 노드로 돌아간다

3. 방문 가능한 모든 노드를 방문할 떄 까지 반복한다.

 

주의할점

노드 방문시 방문 여부를 반드시 검사해야한다

그렇지 않으면 무한루프에 빠질수 있다

 

장점

현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 적다

목표노드가 깊을때 해를 빨리 구할수 있다

 

단점

해가 없는 경로에 깊이 빠질 가능성이 존재

얻어진 해가 최단 경로가 된다는 보장을 얻을수없다

경로가 다수인 문제인 문제에 대해 DFS는 해에 다다르면 탐색이 끝나버리므로

이떄 얻어진해는 최적이 아닐수있음

 

A를 Push함

 

B를 Push함

 

D를 Push함

D노드는 더 깊은 노드가 없음으로 D를 POP 함

 

E를 Push함

 

B와 E노드는 더 깊은 노드가 없음으로 POP 함

 

C를 Push함

 

F를 Push함

 

A,C,F는 더 깊은 노드가 없음으로 FCA순서대로 POP

 

이런 DFS의 구조가 있다고 해보자

 

DFS 구조로 계산될때 1 2 7 6 8 3 4 5 가 나올것이다

1. 시작노드 는 1이다

1번 노드에서 연결된 노드는 작은 순서부터 탐색한다 2, 3, 8 첫번째로 2번노드로 간다

2번노드에서 인접한노드는 1,7노드 1은 이미 방문했었기때문에 7번노드로 간다

7번노드에서는 2번노드는 이미 방문했기때문에 6번노드로 간다

6번노드는 7번노드가 이미 방문했기때문에 8번노드로 간다

3번노드로 되돌아와서 4번으로 갔다가 5번을 방문한다

그래서 계산되는값은 1 2 7 6 8 3 4 5 이다

 

 

재귀함수로구현하기

//해당 그림의 DFS 코드
#include <iostream>
#include <vector>

using namespace std;
//방문여부 0 ~ 8
bool visited[9];
vector<int> graph[9];

void DFS(int x)
{
	visited[x] = true;
	cout << x << " ";

	//인접한 노드 y를 찾는다
	for (int i = 0; i < graph[x].size(); i++)
	{
		//해당 인접한 노드 y가 만약 방문하지않았다면
		int y = graph[x][i];
		if (!visited[y])
		{
			//재귀적으로 방문하라
			DFS(y);
		}
	}
	
}

int main(void)
{
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

	graph[2].push_back(1);
	graph[2].push_back(7);

	graph[3].push_back(1);
	graph[3].push_back(4);
	graph[3].push_back(5);

	graph[4].push_back(3);

	graph[5].push_back(3);

	graph[6].push_back(7);
	graph[6].push_back(8);

	graph[7].push_back(2);
	graph[7].push_back(6);

	graph[8].push_back(1);
	graph[8].push_back(6);

	//루트 설정
	DFS(1);
}

 

 

스택으로 구현하기

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

void DFS(int start)
{
	stack<int> stk;
	//시작 노드 넣기
	stk.push(start);

	while (!stk.empty())
	{
		//스택에서 노드 한개 꺼내기
		int x = stk.top();
		stk.pop();

		//방문하지않았다면
		if (!visited[x])
		{
			//방문 표시 해주기
			visited[x] = true;
			cout << x << " ";

			//인접한 노드를 스택에 넣는다
			//단 뒤에서부터 넣어야 작은 번호부터 넣음
			for (int i = graph[x].size() - 1; i >= 0; i--)
			{
				int y = graph[x][i];
				//인접한 노드 y중에 방문한곳이 있다면 
				if (!visited[y])
				{
					//방문하지 않은 인접노드 y를 스택에 넣는다
					stk.push(y);
				}
			}
		}
	}
}

int main (void)
{
	// 그래프 초기화
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

	graph[2].push_back(1);
	graph[2].push_back(7);

	graph[3].push_back(1);
	graph[3].push_back(4);
	graph[3].push_back(5);

	graph[4].push_back(3);

	graph[5].push_back(3);

	graph[6].push_back(7);
	graph[6].push_back(8);

	graph[7].push_back(2);
	graph[7].push_back(6);

	graph[8].push_back(1);
	graph[8].push_back(6);

	// DFS 시작 (1번 노드부터)
	DFS(1);

	return 0;
}

 

 

 

 

 

BFS (Breadth First Search)

너비 우선 탐색

 

동작방식

구현방식

큐 자료구조 사용

 

구현순서 

그래프에서 행 순서대로 즉 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘

 

 

규칙

그래프의 정점 1노드 방문

그다음 가까운 순서대로 2 3 4 5 6 78 9 10 노드 방문

 

사용하는곳

특정 조건의 최단 경로 알고리즘계산할떄 사용

 

해당 그래프를 BFS로 한다면 방문순서가

1번노드에서 인접한 2 3 8번노드 방문처리

2번노드와 인접한 노드 7번 방문처리 

3번노드와 인접한 4 5번 방문처리

가장먼 노드 6번노드 방문처리

1 2 3 8 7 4 5 6 순서가 된다 

 

 

장점

출발노드에서 목표노드까지의 최단 길이를 무조건 보장한다

 

단점

경로가 많이 길때에는 많은 기억 공간을 필요로하다

무한그래프일경우 해를 찾지도 끝내지도못한다

#include <queue>
#include <iostream>
#include <vector>

using namespace std;

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

void BFS(int start)
{
	queue<int> que;
	que.push(start);
	visited[start] = true;
	
	//큐가 빌떄까지 반복
	while (!que.empty())
	{
		int x = que.front();
		que.pop();
		cout << x << " ";
		for (int i = 0; i < graph[x].size(); i++)
		{
			//인접한 노드 y찾기
			int y = graph[x][i];
			//인접한 노드 y가 방문하지않았다면
			if (!visited[y])
			{
				que.push(y);
				visited[y] = true;
			}
		}
	}
}


int main()
{
	// 그래프 초기화
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

	graph[2].push_back(1);
	graph[2].push_back(7);

	graph[3].push_back(1);
	graph[3].push_back(4);
	graph[3].push_back(5);

	graph[4].push_back(3);

	graph[5].push_back(3);

	graph[6].push_back(7);
	graph[6].push_back(8);

	graph[7].push_back(2);
	graph[7].push_back(6);

	graph[8].push_back(1);
	graph[8].push_back(6);

	// DFS 시작 (1번 노드부터)
	BFS(1);

	return 0;
}