[알고리즘] 그래프 탐색 2가지 - 깊이 우선 탐색(Depth First Search) & 너비우선탐색(Breadth First Search)/ C++ 구현

배열이나 링크드리스트에서는 특정 데이터를 찾기위해 순차 탐색, 이진 탐색을 사용. 이진 탐색트리에서도 이진탐색을 사용한다. 근데 그래프에서는?? 이와같은 방법들이 쉽게 통하지 않는다.  대표적인 기법 2가지가 있다. 바로 깊이우선탐색과 너비우선탐색이다.

 

 

 

깊이 우선 탐색(DFS) (길 끝까지 깊이 들어간다.) 재귀활용 (or stack stl를 활용)

설명 : 최상단노드부터  말단 노드까지 빠르게 내려가면서 탐색하는 방법으로 보통 경우의 수를 확인 할 때

(사용 예: 바둑, 장기 등)

1. 시작정점을 방문표시

2. 해당 정점과 이웃하고 있는 정점중 아직 방문표시 없는곳을 선택하고 시작정점으로 삼고 dfs시작 다시 1번.

3. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2번.

4. 이전 정점으로 돌아가도 더 이상 방문표시 안한곳이 없으면 종료

 

장점 : 방문한 표시를 하며 하나의 말단 노드까지 빠르게 진행. 그리고 다시 돌아와 방문하지 않는 노드로 진행

단점 : 그래프가 깊어질 수록 시간이 많이 소요. 

 

너비 우선 탐색(BFS)(근처 주변을 다 살핀다.) queue stl 활용

설명:  시작 정점을 지나면 깊이가 1인 모든 정점 방문, 그 다음 깊이가 2인 정점 모두 방문...반복

1. 시작 정점을 방문표시후 큐에 삽입

2. 큐로부터 맨앞 정점을 제거. 제거한 정점이 이웃하고 있는 인접 정점 중 방문 표시 없는 곳들을 방문표시 후 큐에 삽입.

3. 큐가 비게 되면 탐색 종료됨. 큐가 빌때까지 2번 과정 반복

 

장점 : 루트노드 부터 특정 노드까지 최단 경로를 찾는데 주로 사용. 상단 노드부터 하나씩 차례대로 탐색하기 때문에 어느시점에 탐색을 종료해도, 그 시점까지 최적의 해를 항상 찾을 수 있다.

단점 : 그래프가 깊어질수록 큐 저장 노드의 개수가 많아짐.

 

 

큰 그래프와 시간 제약이 있다면 깊이 우선 탐색(DFS)은 한쪽 방향의 탐색은 마치고 다른쪽은 가보지도 못할듯. 

 

c++ 코드 

 

방문확인 visited 배열과 노드값 _adj 변수 크기는 임의로 크게 해놓았다.

방문 초기화 함수(SetNewVisited)도 임의로 만들어 놓았다.

 

 

 

 

넓이 우선 탐색

깊이 우선 탐색 (스택)

 

깊이 우선 탐색 (재귀)

실행부분

 

 

결과 

DFS BFS.txt

0.00MB

 

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

 class Graph {
 public:
	 int visited[100] = { 0 };
	 vector<int> _adj[100];
     
	 void AddEdge(int a, int b); //그래프추가 
     
	 void SetNewVisited() {  //방문기록 초기화
		 for (int i = 0; i < 100; i++)
			 visited[i] = 0;
	 };
     
	 void bfs(int start); //큐활용

	 void dfsR(int start); //재귀활용
	 void dfs(int start); //스택활용
 };
 
void Graph::AddEdge(int a, int b){
	_adj[a].push_back(b);
	_adj[b].push_back(a);
 }//end of void Graph::AddEdge
 
 void Graph::bfs(int start) 
 {
	queue<int> q;
	 q.push(start);
	 visited[start] = true;
	 while (!q.empty()) 
     {
		 // 큐에 값이 있을경우 계속 반복 실행 // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다.
		 int x = q.front(); q.pop();
		 cout << x<<" " ;
		 int temp = _adj[x].size();
		 for (int i = 0; i < temp; i++)
         {
			 int y = _adj[x][i];
			 if (!visited[y])// 방문하지 않았다면
             { 
				 q.push(y);
				 visited[y] = true;
			 }
		 }
	 }
 }



 void Graph::dfsR(int start)
 {	 
	 if (visited[start])	// 방문한경우 바로 빠져나옴 
		 return;	

	visited[start] = true;
	cout << start << " ";

	int temp = _adj[start].size();
	for (int i = 0; i < temp; i++)
    {
		int next_node = _adj[start][i];

		if (visited[next_node] == false) 
        {
			 dfsR(next_node);
		}
	}
}//end of void Graph::dfsR
 
 void Graph::dfs(int start)
 {
	 stack<int> s;
	 s.push(start);
	 visited[start] = true;
	 cout << start << " ";

	 while (!s.empty())
     {
		 int current_node = s.top();s.pop();
		 int temp=_adj[current_node].size();

		 for (int i = 0; i < temp; i++) 
         {

			 int next_node = _adj[current_node][i];

			 if (visited[next_node] == false)
             {
				 cout << next_node << " ";
				 visited[next_node] = true;

				 s.push(current_node);
				 s.push(next_node);
				 break;
			 }
		 }
	 }
 }//end of void Graph::dfs

 int main() {	 
	 Graph FirstG;
	 FirstG.AddEdge(1, 2);
	 FirstG.AddEdge(1, 3);
	 FirstG.AddEdge(2, 4);
	 FirstG.AddEdge(2, 5);
	 FirstG.AddEdge(4, 8);
	 FirstG.AddEdge(5, 9);
	 FirstG.AddEdge(3, 6);
	 FirstG.AddEdge(3, 7);

	 cout << "BFS(큐) 알고리즘 시작 " << endl;
	 FirstG.bfs(1);
	 FirstG.SetNewVisited();
	 cout << endl;
	 cout << endl;

	 cout << "DFS(스택) 알고리즘 시작 " << endl;
	 FirstG.dfs(1);
	 FirstG.SetNewVisited();
	 cout << endl;
	 cout << endl;

	 cout << "DFS(재귀) 알고리즘 시작 " << endl;
	 FirstG.dfsR(1);
	 cout << endl;
}//end of main