BFS / DFS

BFS / DFS

[참고 사이트]
https://blog.encrypted.gg/1016

https://velog.io/@orcasuit/BFSBreadth-First-Search%EC%9D%98-%EC%A0%95%EC%9D%98%EC%99%80-%ED%8A%B9%EC%A7%95

https://velog.io/@orcasuit/DFSDepth-First-Search%EC%9D%98-%EC%A0%95%EC%9D%98%EC%99%80-%ED%8A%B9%EC%A7%95-a3qlllyy

https://suyeon96.tistory.com/32

BFS(너비우선 탐색)(거리)

특정 노드에서 시작하여 인접한 노드를 먼저 탐색해 나가는 방법.(가까운 정점부터)

작동 순서(큐 사용)

1. 시작하는 정점을 큐에 넣고 방문했다는 표시 남김
2. 큐에서 정점을 꺼내서 그 정점과 연결된 모든 정점들에 대해 3번 진행
3. 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음 방문했으면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복합니다.

모든 정점이 큐에 최대 1번씩 들어가므로 인접 행렬에서 O(V^2), 인접 리스트에서 O(V+E)시간 복잡도 존재

특징

• 단계별 탐색: 가까운 정점을 먼저 방문, 인접한 정점 방문
• 탐색 순서 기록: 각 정점이 방문되는 순서가 레벨별로 수행
• 큐 사용: 방문할 정점을 큐에 저장하여 처리
• 시간 복잡도: 일반적으로 O(V+E)이다.
• 최단 경로: 시작 정점에서 다른 정점까지 최단 경로를 찾을 때 사용

밑의 코드는 슈도코드와 파이썬을 결합한 BFS 코드이다.(김윤호님 작성)

BFS(G, s)
	for each_Node u ∈ G.V -{s}
	## 초기화 코드
		u.color = WHITE
		u.d = ∞
		u.π = null
	
	s.color = GRAY
	s.d = 0
	s.π = NULL
	## 회색 친구들 저장소
	Q = []
	Q.insert(s)
	while len(Q) != 0		## 종료 조건으로 모든 정점이 발견 되어서 종료시켜도 됨
		u = Q.pop()
		## 배열에 저장되어져 있는 친구들 전부다 확인
		## 여기서 원하는 조건 찾으면 종료해도 됨, 하지만, BFS는 전체탐색의 의의도 있으니 아닌 경우도 많음
		for G.adj[u] 에 있는 각 정점 v
			if v.color == WHITE
				v.color = GRAY ## 탐색 기준의 대상
				v.d = u.d+1 ## 대상의 거리는 지금 거리보다 1 큼
				v.π = u ## 그친구의 부모노드는 나다
				Q.insert(s)
		u.color = BLACK

DFS(타임 스탬프)

특정 노드에서 시작하여 다음 가지로 넘어가기 전에 해당 분기를 완벽하게 탐색함. 모든 정점을 방문

작동 순서(스택 사용)

1. 시작하는 정점을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 정점을 꺼내서 그 정점과 연결된 모든 정점들에 대해 3번을 수행
3. 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기로 해당 칸을 스택에 삽입
4. 스택이 빌 때 까지 2번 반복

BFS와 같이 모든 정점이 스택에 최대 1번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V^2)의 시간 복잡도 존재

특징

• 깊이 우선 탐색: 가능한 한 깊게 탐색하고, 더 이상 탐색할 곳이 없으면 이전 정점으로 돌아가 다음 경로를 탐색
• 스택(Stack) 또는 재귀 사용: 보통 스택이나 재귀를 사용하여 구현
• 백트래킹: 문제 해결을 위한 경로를 찾을 때 유용, 해가 없는 루트는 즉시 포기하고 다시 이전 단계로 돌아감
• 시간 복잡도: 일반적으로 O(V + E)
• 발견 시간과 종료 시간은 괄호 구조를 가진다(종료가 되야한다)(타임스탬프)

밑의 코드는 슈도코드와 파이썬을 결합한 DFS 코드이다.(김윤호님 작성)

DFS(G)
	for each_Node u ∈ G.V -{s}
	## 초기화 코드
		u.color = WHITE
		u.π = null
	time = 0
	for each_Node u ∈ G.V -{s}
		if u.color = WHITE
			DFS-VISIT(G, u)

DFS-VISIT(G, u)
	time = time + 1  ## 흰색 정점에 u가 발견되면 시간을 업데이트 후
	u.d = time ## 저장
	u.color = Gray 
	for G.adj[u] 에 있는 각 정점 v ## 각 간선(u, v)을 탐색
		if v.color == WHITE
		 	v.π = u
		 	DFS-VISIT(G, v)
time = time + 1
u.f = time
u.color = BLACK ## 끝나면 검정색이용

BFS와 DFS의 장단점

파이썬에서는 BFS와 DFS를 라이브러리를 활용하여 쉽게 구현가능합니다.
구현과 관련된 정보는 https://velog.io/@tks7205/dfs%EC%99%80-bfs%EB%A5%BC-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%97%AC%EB%9F%AC%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95-in-python 해당 블로그를 참조해보자.