그래프의 순회 - BFS, DFS

그래프의 순회는 그래프의 모든 정점을 방문하여 데이터를 확인하는 알고리즘이다.

 

BFS - 넓이 우선 탐색

DFS - 깊이 우선 탐색

 

두 가지가 있으며 다양한 알고리즘에 활용되는 기본 연산 느낌이다.

 

막상 처음 접하면 어렵지만 배우고 나면 쉬운 개념의 알고리즘이다.

 

처음엔 그래프 구조와 큐를 사용한다는 점을 떠올리지 못해서 어려웠던 것 같다.

 

BFS

그래프 정점에 방문했을 때, 간선이 방문하지 않은 정점을 가르키면 큐에 넣는다.

큐에 넣을 때, 방문을 한 것으로 간주하고 큐에 넣는다.

방문한 정점은 방문했다고 표시 >> 안해도 될듯

큐에서 정점 하나를 꺼내서 위의 과정을 반복 

큐가 비면 종료

void Graph::BFS(VORTEX* visit) {
	EDGE* temp = visit->Ehead;
	VORTEX* next = nullptr;

	visit->visited = true;
	std::cout << visit->Data << " ";

	while (temp) {
		if (!temp->to->visited) {
			q.push(temp->to);
			temp->to->visited = true;
		}
		temp = temp->next;
	}
	if (!q.empty()) {
		next = q.front();
		q.pop();

		BFS(next);
	}
}

 

DFS 

그래프 정점에 방문하고 방문으로 표시함

그래프의 간선을 통해 다음 정점으로 이동 >> 반복

void Graph::DFS(VORTEX* visit) {
	EDGE* temp = visit->Ehead;
	VORTEX* next = nullptr;

	visit->visited = true;
	std::cout << visit->Data << " ";

	while (temp) {
		if (!temp->to->visited) {
			next = temp->to;

			DFS(next);
		}
		temp = temp->next;
	}
}