자료구조 BFS

Tree BFS 탐색 순서

BFS는 레벨 단위로 탐색을 한다. 즉 한 번 만에 갈 수 있는 길을 모두 탐색한후, 두 번 만에 갈수 있는 모든 길을 탐색하는 방식이다.

BFS의 특징

두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다. 멀리떨어진 노드는 나중에 탐색하는 방식이기 때문!

큐를 활용해서 탐색할 노드의 순서를 저장하고 큐에 저장된 순서대로 탐색한다. 선입선출의 방식을 활용해야 하기 때문에 큐를 활용한다.

BFS 구현 알고리즘

루트노드에서 시작한다.

루트노드와 인접하고 방문된적 없고, 큐에 저장되지 않은 노드를 Queue에 넣는다.

Queue에서 dequeue(pop)하여 가장 먼저 큐에 저장한 노드를 방문한다.

---

BFS의 과정

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크) → 큐에 방문된 노드를 삽입(enqueue)한다. → 초기 상태의 큐에는 시작 노드만이 저장 → 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
2. 1. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다. → 큐에서 꺼낸 노드를 방문한다. → 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다. → 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
3. 큐에 방문된 노드를 삽입(enqueue)한다. 큐가 소진될 때까지 계속한다.

#include <iostream>

int map[6][6] =
{
	{0, 1, 1, 0, 0, 0},
	{0, 0, 0, 1, 1, 0},
	{0, 0, 0, 0, 0, 1},
	{0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0}
};

char value[6] = { 'E', 'A', 'U', 'R', 'Q', 'Y' };

struct Node
{
	int num;
	int level;
};

Node queue[7] = { {0,0} };
int head = 0;
int tail = 1;

int main()
{
	while (head != tail)
	{
		Node now = queue[head];
		std::cout << value[now.num] << std::endl;
		std::cout << "------------" << std::endl;

		for (int i = 0; i < 6; i++)
		{
			if (map[now.num][i] == 1)
			{
				queue[tail] = { i, now.level + 1 };
				tail++;
			}
		}

		head++;
	}

    return 0;
}

---

라이브러리를 사용한 방법

#include <iostream>
#include <queue>

int map[6][6] =
{
	{0, 1, 1, 0, 0, 0},
	{0, 0, 0, 1, 1, 0},
	{0, 0, 0, 0, 0, 1},
	{0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0}
};

char value[6] = { 'E', 'A', 'U', 'R', 'Q', 'Y' };

struct Node
{
	int num;
	int level;
};

std::queue<Node> queue = {};

int main()
{
	queue.push(Node{0, 0});

	while (!queue.empty())
	{
		Node now = queue.front();

		std::cout << value[now.num] << std::endl;
		std::cout << "------------" << std::endl;

		for (int i = 0; i < 6; i++)
		{
			if (map[now.num][i] == 1)
			{
				queue.push(Node{ i, now.level + 1 });
			}
		}

		queue.pop();
	}

    return 0;
}

BFS의 시간복잡도

인접 리스트 → O(N+E)

인접 행렬 → O(N^2)