[Algorithm] BFS,DFS 알고리즘 구현(C++)

본 글에서는 IDE로 DEV C++을 사용하였다.

---

그래프 만들기

---

보통 그래프를 입력받을 때에는 파일로 받는 경우가 많다.

본 글에서는 txt파일을 사용하였다.

graph_1.txt

graph_1이라는 txt파일을 만들었다.

맨 위의 13은 vertex의 개수이고 12는 edge의 개수이다.

 

밑의 영어들은 트리 구조의 그래프이다.

해당 파일은 프로젝트 내부에 위치해야 한다.

---

구현

---

먼저 코드 블럭 단위로 리뷰를 할 것이다.

리뷰 순서는 앞선 글에서의 실행 순서와 같다.

2023.01.29 - [CS/알고리즘(Algorithm)] - [Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본

[Algorithm] 그래프 탐색 알고리즘(BFS, DFS) 기본

만약 BFS, DFS의 실행 순서를 모른다면 위 글을 참고하면 된다.

 

그래프 선언

using namespace std;

class Graph
{
public:
	int nV, nE;//vertex, edge 개수를 담을 변수
	vector<int>* edges;//각 vertex들을 담을 연결리스트
	void Init(const char* _filename)
	{
		printf("%s\n", _filename);//파일 이름 출력
		FILE* input = fopen(_filename, "r");
		fscanf(input, "%d", &nV);//vertex의 개수
		fscanf(input, "%d", &nE);//edge의 개수
		edges = new vector<int>[nV];//vertex를 담을 수 있는 연결리스트
		for (int i = 0; i < nE; i++)
		{
			char a, b;
			fscanf(input, " %c %c", &a, &b);
			printf("%c, %c\n", a, b);//먼저 문자 출력
			int x, y;//정수형으로 mapping해야 하므로 정수형 변수 2개 선언
			x = a - 'A';
			y = b - 'A';//vertex를 정수형으로 변환
			printf("%d %d\n", x, y);
			edges[x].push_back(y);//x 뒤에 y변수에 해당하는 데이터를 계속 추가해줌
		}
		fclose(input);
	}
};

먼저 그래프 파일을 입력받기 위한 클래스를 선언한다.

그리고 vertex와 edge를 저장할 정수형 변수 2개를 선언한다.

vertex가 어디에 어떻게 연결되어 있는지 구조를 알아야 하기 때문에 연결리스트(vector)를 사용한다.

 

먼저 메모장에 저장한 파일형태의 그래프를 파일포인터를 사용하여 연다.

vertex와 edge의 개수를 각각 nV와 nE에 저장한다.

노드를 담을 수 있는 연결리스트를 선언한다. vertex값이 들어가야 하기 때문에 nV변수의 값이 들어가야 한다.

연결리스트는 edge와 같은 역할을 한다.

 

이제 반복문을 nE 즉 edge의 수만큼 돌린다.

해당 프로그램에서는 A = 0 B = 1 이런식으로 정수형으로 mapping을 하는 형태이기 때문에 정수형 변수 x, y를 선언하고 A를 빼서 문자를 숫자형으로 변환시킨다.

이제 x 변수에 y변수값을 push_back 하는 형태로 연결리스트에 그래프 연결을 표현한다.

 

BFS

void BFS(Graph& _g, int _stIdx = 0)//Graph클래스 상속, 시작 노드 0
{
	bool* visit = new bool[_g.nV];//Graph 클래스의 nV변수를 이용해서 vertex개수를 참고
	for (int i = 0; i < _g.nV; i++)
	{
		visit[i] = false;//vertex를 전부 false(미방문)으로 마킹
	}
	queue<int> q;
	q.push(_stIdx);//시작 노드에 해당하는 값 넣어줌. 해당 코드에서는 A = 0
	visit[_stIdx] = true;//방문한 노드는 true로 마킹
	while (!q.empty())
	{
		int x = q.front();//큐가 비어있지 않으면 x를 통해 큐의 front를 참조
		q.pop();//front에 해당하는 vertex를 삭제
		printf("%c", x + 'A');//삭제 후 다시 A를 더해서 문자형으로 출력
		for (int i = 0; i < _g.edges[x].size(); i++)//x의 인접 노드(y)중 한번도 큐에 들어가지 않은 값 탐색
		{
			if (!visit[_g.edges[x][i]])//만약에 i노드가 방문하지 않은 상태라면?
			{
				q.push(_g.edges[x][i]);//큐에 넣는다.
				visit[_g.edges[x][i]] = true;//넣은 후 방문했다고 마킹
			}
		}
	}
	delete[] visit;//visit에 할당한 값 삭제
}

먼저 Graph 클래스를 _g 라는 이름으로 상속받는다.

그리고 Graph 클래스의 nV변수를 이용하여 파일 데이터의 vertex 개수를 참고한다.

후에 vertex의 마킹값을 반복문을 이용하여 전부 false로 초기화한다.

 

BFS에서는 큐 자료구조를 사용하기 때문에 먼저 큐를 선언한다.

큐를 선언한 후 시작 노드를 지정해 준다.

해당 코드에서는 A 즉 0이 시작 노드이다.

그리고 0에 해당하는 노드를 true로 마킹하여 다시 큐에 들어가지 않도록 선언해 준다.

 

이제 큐가 빌 때까지 반복하는 반복문을 작성한다.

int x를 큐의 front pointer로 지정하고 큐가 비어있지 않으면 x를 통하여 큐의 front를 참조할 수 있도록 설계한다.

큐에서 빠진 노드는 문자열로 출력이 되게끔 다시 A를 더해준다.

 

이제 Graph 클래스의 y변수에 해당하는 값, 즉 인접 노드 중 한번도 큐에 들어가지 않은 노드를 찾아서 큐에 push한 후 true로 마킹한 후 pop, 출력을 반복한다.

 

마지막으로 visit에 할당한 값을 삭제한다.

 

DFS

void DFS(Graph& _g, int _stIdx = 0)
{
	bool* visit = new bool[_g.nV];
	for (int i = 0; i < _g.nV; i++)
	{
		visit[i] = false;
	}
	stack<int> s;
	s.push(_stIdx);
	visit[_stIdx] = true;
	while (!s.empty())
	{
		int x = s.top();
		s.pop();
		printf("%c", x + 'A');
		for (int i = 0; i < _g.edges[x].size(); i++)
		{
			if (!visit[_g.edges[x][i]])
			{
				s.push(_g.edges[x][i]);
				visit[_g.edges[x][i]] = true;
			}
		}
	}
	delete[] visit;
}

위의 코드를 잘 이해했다면 DFS도 이해하기 쉬울 것이다. 진짜 똑같아서 다시 주석달고 설명글을 쓰기 귀찮다.

똑같은 방식으로 작성된 코드인데 사용된 자료구조가 stack으로 바뀌었을 뿐이다.

---

전체코드

---

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <queue>
#include <stack>


using namespace std;

class Graph
{
public:
	int nV, nE;
	vector<int>* edges;
	void Init(const char* _filename)
	{
		printf("%s\n", _filename);
		FILE* input = fopen(_filename, "r");
		fscanf(input, "%d", &nV);
		fscanf(input, "%d", &nE);
		edges = new vector<int>[nV];
		for (int i = 0; i < nE; i++)
		{
			char a, b;
			fscanf(input, " %c %c", &a, &b);
			printf("%c, %c\n", a, b);
			int x, y;
			x = a - 'A';
			y = b - 'A';
			printf("%d %d\n", x, y);
			edges[x].push_back(y);
		}
		fclose(input);
	}
};

void BFS(Graph& _g, int _stIdx = 0)
{
	bool* visit = new bool[_g.nV];
	for (int i = 0; i < _g.nV; i++)
	{
		visit[i] = false;
	}
	queue<int> q;
	q.push(_stIdx);
	visit[_stIdx] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		printf("%c", x + 'A');
		for (int i = 0; i < _g.edges[x].size(); i++)
		{
			if (!visit[_g.edges[x][i]])
			{
				q.push(_g.edges[x][i]);
				visit[_g.edges[x][i]] = true;
			}
		}
	}
	delete[] visit;
}

void DFS(Graph& _g, int _stIdx = 0)
{
	bool* visit = new bool[_g.nV];
	for (int i = 0; i < _g.nV; i++)
	{
		visit[i] = false;
	}
	stack<int> s;
	s.push(_stIdx);
	visit[_stIdx] = true;
	while (!s.empty())
	{
		int x = s.top();
		s.pop();
		printf("%c", x + 'A');
		for (int i = 0; i < _g.edges[x].size(); i++)
		{
			if (!visit[_g.edges[x][i]])
			{
				s.push(_g.edges[x][i]);
				visit[_g.edges[x][i]] = true;
			}
		}
	}
	delete[] visit;
}

int main(int argc, char** argv)
{
	Graph g;
	g.Init(argv[1]);

	printf("\n");
	printf("BFS: ");
	BFS(g);
	printf("\n");
	printf("DFS: ");
	DFS(g);
	printf("\n");

	return 1;
}

전체 코드는 다음과 같다.

main함수에서 그래프 파일을 command line에서 받을 수 있도록 argc, argv를 매개변수로 준다.

Graph를 g로 선언한 후, BFS와 DFS를 실행한다.

실행 결과

실행 결과는 다음과 같다.

각 vertex들의 정수값과 BFS DFS 탐색 결과까지 잘 출력된다.