[ALGOS STUDY] 2023-SUMMER DAY2 그래프, DFS/BFS

그래프

- 그래프 : 정점(노드)과 간선(링크)으로 이루어진 자료구조의 일종

- 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것

 

DFS

- 깊이 우선 탐색 (Depth-First Search) : 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드 pop
3. 2번의 과정을 수행할 수 없을 때까지 반복

- 특징

• 스택을 활용한 구현, 재귀함수를 통한 구현이 가능함.
• 공간복잡도가 낮음.
• 목표 노드가 깊이 있을 경우 빠르게 탐색이 가능함.
• 해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색이 진행됨
• 최단 경로를 보장하지 않음.
• 경로의 특징을 저장해야 하는 문제에서 사용 가능함.

 

BFS

- 너비 우선 탐색 (Breadth-First Search) : 인접한 노드를 먼저 탐색

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복

- 특징

• 최단 경로를 보장함.
• 노드의 수가 작고 깊이가 얕은 해가 존재할 때 유리
• 노드의 수가 많을수록 많은 메모리가 필요

- 문제 풀이 예시 : 백준 1260 DFS와 BFS (https://www.acmicpc.net/problem/1260)

#include <iostream>
using namespace std;

int n, m, v, visited_dfs[1001] = { 0, }, visited_bfs[1001] = { 0, }, arr[1001][1001], queue[1001];

void dfs(int v)
{
	cout << v << " ";
	visited_dfs[v] = 1;
	for (int i = 1; i <= n; i++) if (arr[v][i] == 1 && visited_dfs[i] == 0) dfs(i);
}

void bfs(int v)
{
	int front = 0, rear = 0;
	cout << v << " ";
	visited_bfs[v] = 1;
	queue[rear++] = v;
	while (front < rear)
	{
		int pop = queue[front++];
		for (int i = 1; i <= n; i++)
		{
			if (arr[pop][i] == 1 && visited_bfs[i] == 0)
			{
				cout << i << " ";
				queue[rear++] = i;
				visited_bfs[i] = 1;
			}
		}
	}
}

int main()
{
	cin >> n >> m >> v;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}

	dfs(v);
	cout << "\n";
	bfs(v);
	return 0;
}

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 일시 자료는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다. 

 

<출처>

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) (velog.io)

[ALG] DFS/BFS (깊이/너비 우선탐색) (hudi.blog)

[ALG] DFS/BFS (깊이/너비 우선탐색) (hudi.blog)

[Python] DFS & BFS (tistory.com)

DFS, BFS의 설명, 차이점 (velog.io)

 

ALGOS 2023 여름방학 캠프의 경우 저는 주제 총정리 영상을 담당하였습니다. 5일동안의 주제를 간단히 정리하는 영상을 제작하였으며, 해당 글과 발표자료 제작 시 참고한 내용의 출처는 다음과 같습니다.

 

<출처>

파이썬으로 배우는 자료구조 프로그래밍 (유석종)

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
https://velog.io/@taeil314/Data-StructureC-%EA%B7%B8%EB%9E%98%ED%94%84-Graph

https://hudi.blog/dfs-bfs/