깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) - 14장 (2)

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

이름에서 알 수 있듯이 깊이를 우선하여 탐색한다.

즉 탐색의 진행 방향에 있어서 순서상으로 만나는 정점을 대상으로 바로 탐색을 진행한다.

그러다가 더이상 탐색을 진행할 곳이 없다면 이때까지 방문했던 녀석들을 하나씩 돌아가면서

다른 정점을 방문할 수 있는지 체크한다.

 

우선 DFS의 과정을 그림으로 살펴본다.

위 그림에서도 보이듯이 탐색의 진행이 한 길을 깊이 파고든다.

(누구를 먼저 선택할 것인지에 대한 것은 구현하는 이가 결정)

그러다가 그림 3에서 길이 막힌다면 역으로 돌아가면서 

수정->정희->민석까지 돌아가다가 아직 방문안한 지율을 방문하고 다시 시작점으로 돌아간다.

(시작점으로 돌아가는 이유는 방문안한 녀석들을 돌아오면서 다시 다 체크하기 위함)

 

즉 방문순서를 말해보면

동수->지민->민석->정희->수정(막힘 연결된 정점들은 이미 모두 방문하였음 -> 돌아간다)->정희->민석->지율

->민석->지민->동수.

 

깊이 우선 탐색에서 정점을 타고간 길을 기억하기 위해 '스택' 자료구조가 사용이 된다.

(재귀를 통해서도 구현이 가능)

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

DFS가 한 사람(정점)에게 연락을 쭉 취하는 방식이라면, BFS는 자신과 연결된 모든 사람(정점)에게 연락을 취하는 방식.

 

BFS는 자신과 연결된 모든 사람(정점)을 먼저 방문한다.

즉 지율에서 부터 BFS가 시작된다고 하면, 지율은 동수,민석순으로 방문을 하게 된다.

그리고 먼저 방문한 동수를 대상으로 자신과 연결된 정점들을 방문. (지율은 방문했으니 지민)

동수의 탐색이 끝나고 그 다음 순서로 방문한 민석의 기준으로 탐색.

지율과 지민은 이미 방문을 했으므로 수정과 정희순으로 탐색을 진행. 

 

이런식으로 BFS는 탐색을 진행한다.

 

BFS는 먼저 들어온 녀석의 다음 정점들을 방문을 위해 '큐' 자료구조를 사용한다.

 

깊이 우선 탐색 구현 모델

앞서 DFS를 구현하기 위한 필요 자료구조는 스택이라 하였다.

사실 하나가 더 필요한데 그것은 방문 정보를 기록하는 배열이 필요하다.

 

스택은 탐색을 진행하면서 더 이상 방문할 곳이 없다면 돌아갈 길을 기억하기 위해 사용.

배열은 다음 정점을 방문하는데 그 정점이 방문했는지 안했는지 판별하기 위해 사용.

 

즉 위 그림과 같이 진행이 된다.

 

그리고 DFS는 알고리즘이기에 그래프를 표현하는 데이터를 받는다면 따로 함수만 만들어서 처리가 가능하다.

 

하지만 여기서는 클래스를 만들고 거기 안에서 DFS를 구현한다.

 

우선 ALGraphDFS.h

#pragma once
class LinkedList;
class ALGraphDFS
{
public:
	ALGraphDFS() = delete;
	ALGraphDFS(int inputV);
	~ALGraphDFS(); // adjList해제.
	void AddEdge(int fromV, int toV); // 간선 추가
	void ShowGraphEdgeInfo(); // 간선 정보 출력
	bool VisitVertex(int visitV); // 정점의 방문을 체크하는 함수.
	void DFShowGraphVertex(int startV); // DFS
	
private:
	int numV; // 정점의 수
	int numE; // 간선의 수
	int* visitInfo; // 방문 정보를 기억하기 위한 배열. (bool배열로도 가능)
	LinkedList* adjList; // 간선의 정보
};

 

그 다음 ALGraphDFS.cpp

#include <iostream>
#include <cstring>
#include "ALGraphDFS.h"
#include "LinkedList.h"
#include "Stack.h"

ALGraphDFS::ALGraphDFS(int inputV) : numV(inputV), numE(0)
{
	adjList = new LinkedList[numV]();
	visitInfo = new int[numV];
	memset(visitInfo, 0, sizeof(int) * numV); // 0으로 초기화.
}
ALGraphDFS::~ALGraphDFS()
{
	delete[] adjList;
	delete[] visitInfo;
}
void ALGraphDFS::AddEdge(int fromV, int toV)
{
	// 무방향 그래프.
	adjList[fromV].push_front(toV);
	adjList[toV].push_front(fromV);
	++numE;
}

void ALGraphDFS::ShowGraphEdgeInfo()
{
	int i, vx;

	for (i = 0; i < numV; ++i)
	{
		std::cout << static_cast<char>(i + 'A') << "와 연결된 정점 : ";

		if (adjList[i].LFirst())
		{
			vx = adjList[i].iterator()->GetData();
			std::cout << static_cast<char>(vx + 'A') << " ";
			while (adjList[i].LNext())
			{
				vx = adjList[i].iterator()->GetData();
				std::cout << static_cast<char>(vx + 'A') << " ";
			}
			std::cout << std::endl;
		}
	}
}

bool ALGraphDFS::VisitVertex(int visitV)
{
	if (visitInfo[visitV] == 0) // 방문안했다면. true
	{
		visitInfo[visitV] = 1;
		//std::cout << static_cast<char>(visitV + 'A');
		return true;
	}
	return false; // 방문했다면 false.
}

void ALGraphDFS::DFShowGraphVertex(int startV)
{
	Stack<int> s;
	int visitCount = 0;
	int visitV = startV;
	int nextV;

	VisitVertex(visitV); // 시작정점은 바로 방문.
	s.Push(visitV); // 스택에 담는다.
	std::cout << static_cast<char>(visitV + 'A') << " 방문." << std::endl;
	++visitCount;
	while (adjList[visitV].LFirst()) // 모든 정점의 방문을 위한 while문
	{
		nextV = adjList[visitV].iterator()->GetData();
		bool flag = false;

		if (VisitVertex(nextV)) // 방문하지 않았다면.
		{
			visitV = nextV; //
			std::cout << static_cast<char>(visitV + 'A') << " 방문." << std::endl;
			s.Push(visitV);
			flag = true;
			++visitCount;
		}
		else // 방문에 실패했다면->길이막혔다면 바로 빠져나오고, 다른 정점이 있다면 그 녀석을 대상으로 방문.
		{
			while (adjList[visitV].LNext())
			{
				nextV = adjList[visitV].iterator()->GetData();
				if (VisitVertex(nextV))
				{
					visitV = nextV;
					std::cout << static_cast<char>(visitV + 'A') << " 방문." << std::endl;
					s.Push(visitV);
					flag = true;
					++visitCount;
					break; 
				}
			}
		}

		if (flag == false) // 추가로 방문한 정점이 없다면.
		{
			if (s.Empty()) // 스택이 비었거나(시작점으로 돌아온상황->끝)
				break;
			else // 길이 막혔거나.
			{
				std::cout << static_cast<char>(visitV + 'A') << "에서 ";
				s.Pop();
				visitV = s.GetTop();
				if (s.Empty() && visitCount == numV)
				{
					std::cout << static_cast<char>(startV + 'A') << ". 시작점 도착 종료. " << std::endl;
					memset(visitInfo, 0, sizeof(int) * numV); // 이후의 탐색을 위해 visitInfo는 초기화.
					return;
				}
				else
					std::cout << static_cast<char>(visitV + 'A') << "로 돌아간다. " << std::endl;
			}
		}
	}

	
	
}

main.cpp

enum // 정점이름 상수화.
{
	A = 0, B, C, D, E, F, G, H, I, J
};

int main()
{
	
	ALGraphDFS a(7);

	a.AddEdge(A, B);
	a.AddEdge(A, D);
	a.AddEdge(B, C);
	a.AddEdge(D, C);
	a.AddEdge(D, E);
	a.AddEdge(E, F);
	a.AddEdge(E, G);

	a.ShowGraphEdgeInfo();

	cout << endl;

	a.DFShowGraphVertex(A);
	return 0;
}

실행결과.

너비 우선 탐색 구현 모델

앞서 구현한 DFS모델에서 BFS의 내용이 붙는다.

 

너비 우선 탐색은 깊이 우선 탐색과는 달리 한 방향으로 계속타고 가는 것이 아닌, 자신과 연결된 정점들을 모두 방문하고 넘어가는 탐색을 진행한다.

 

먼저 너비 우선 탐색도 방문 정보를 기록하기 위한 배열.

그리고 방문한 순서를 기록하기 위한 '큐(배열기반의 환형 큐)'를 사용한다.

 

먼저 ALGraphBFS.h

#pragma once

class LinkedList;
class ALGraphBFS
{
public:
	ALGraphBFS() = delete;
	ALGraphBFS(int inputV);
	~ALGraphBFS(); // adjList해제.
	void AddEdge(int fromV, int toV); // 간선 추가
	void ShowGraphEdgeInfo(); // 간선 정보 출력
	bool VisitVertex(int visitV); // 정점의 방문을 체크하는 함수.
	void BFShowGraphVertex(int startV); // DFS
private:
	int numV; // 정점의 수
	int numE; // 간선의 수
	int* visitInfo; // 방문 정보를 기억하기 위한 배열. (bool배열로도 가능)
	LinkedList* adjList; // 간선의 정보
};

 

그리고 ALGraphBFS.cpp

#include <iostream>
#include <cstring>
#include "ALGraphBFS.h"
#include "LinkedList.h"
#include "Queue.h"

ALGraphBFS::ALGraphBFS(int inputV) : numV(inputV), numE(0)
{
	...앞과 동일
}
ALGraphBFS::~ALGraphBFS()
{
	...앞과 동일
}
void ALGraphBFS::AddEdge(int fromV, int toV)
{
	...앞과 동일
}

void ALGraphBFS::ShowGraphEdgeInfo()
{
	...앞과 동일
}

bool ALGraphBFS::VisitVertex(int visitV)
{
	...앞과 동일
}


void ALGraphBFS::BFShowGraphVertex(int startV)
{
	Queue<int> q;
	int visitV = startV;
	int nextV;

	VisitVertex(visitV); // 시작 정점은 바로 방문.
	std::cout << "시작정점 : " << static_cast<char>(visitV + 'A') << " 방문" << std::endl;
	while (adjList[visitV].LFirst())
	{
		nextV = adjList[visitV].iterator()->GetData();
		if (VisitVertex(nextV))
		{
			q.Enqueue(nextV);
			std::cout << static_cast<char>(visitV + 'A') <<"정점과 연결된 정점 : " << static_cast<char>(nextV + 'A') << " 방문" << std::endl;
		}
			

		while (adjList[visitV].LNext())
		{
			nextV = adjList[visitV].iterator()->GetData();
			if (VisitVertex(nextV))
			{
				q.Enqueue(nextV);
				std::cout << static_cast<char>(visitV + 'A') << "정점과 연결된 정점 : " << static_cast<char>(nextV + 'A') << " 방문" << std::endl;
			}
		}
		// 여기까지가 정점과 연결된 모든 정점들을 큐에 담는 행동.

		if (q.IsEmpty()) // 큐가 비면 종료.
		{
			std::cout << "모든 정점 방문 완료." << std::endl;
			break;
		}
		else // 그게 아니라면 정점과 연결된 모든 정점을 방문했으므로 먼저 방문한 정점을 대상으로 다시 BFS진행.
		{
			std::cout << static_cast<char>(visitV +'A') << "정점과 연결된 정점은 모두 방문 완료." << std::endl;
			visitV = q.Dequeue();
			std::cout << "그 다음 정점 " << static_cast<char>(visitV + 'A') << " 부터 다시 너비 탐색." <<std::endl;
		}
	}

	memset(visitInfo, 0, sizeof(int) * numV);



}

main.cpp와 결과.

enum // 정점이름 상수화.
{
	A = 0, B, C, D, E, F, G, H, I, J
};

int main()
{
	
	ALGraphBFS a(7);

	a.AddEdge(A, B);
	a.AddEdge(A, D);
	a.AddEdge(B, C);
	a.AddEdge(D, C);
	a.AddEdge(D, E);
	a.AddEdge(E, F);
	a.AddEdge(E, G);

	a.ShowGraphEdgeInfo();

	cout << endl;

	a.BFShowGraphVertex(A);
	return 0;
}