BFS, DFS

BFS, DFS

BFS , DFS

BFS와 DFS는 순회(방문)하면서 탐색하는 탐색 알고리즘이다

BFS, DFS는 BFT(breadth-first traversal), DFT(depth-first traversal)이라고도 불리는데, traversal은 트리에서의 순회와 같은 용어다

단, 출발지 노드와 그래프/트리 구조에 따라 탐색하는 순서와 노드가 달라질 수 있다

Breadth-first search 너비우선탐색

큐의 개념이 사용된다(FIFO)

루트부터 저장되고 사용된다

층별로 순서대로 탐색된다

최단경로를 찾기 적합하며, 찾는노드가 인접한경우 보다 효과적이다

하지만 노드의 수가 많을수록 메모리소비가 크다

BFS 길 찾기, 라우팅 BitTorrent와 같은 P2P 네트워크에서 인접 노드 찾기 웹 크롤러 소셜 네트워크에서 멀리 떨어진 사람 찾기 그래프에서 주변 위치 찾기 네트워크에서 방송 그래프에서 주기 감지 연결된 구성 요소 찾기 몇 가지 이론적 그래프 문제 풀기

우선적으로, 그래프의 각 노드를 보고 방문할 노드에 대해 구분한다

모든 verts(정점 또는 노드)를 방문하지 않은 상태(white)이다

다음으로 시작 노드를 gray로 표시한다

gray는 시작 노드의 이웃을 탐색한다

시작 노드를 큐에 넣는다

이는 while 루프에 들어가면 첫 번째 vert가 될 것임을 의미한다

while 루프의 시작 부분에서 확인하는 조건은, 큐가 비어 있지 않은지 여부이다

비어 있지 않으면 큐의 첫 번째 항목을 변수에 저장한다(u = queue[0])

각 이웃의 vert에 대해 반복문 수행한다

방문하지 않았는지(white) 확인한다

방문하지 않은 경우 gray으로 표시한다(이웃을 탐색한다는 의미)

탐색한 현재 vert를 대기열에서 빼고(deque), 해당 vert를 black으로 표시한다(방문한 것으로 표시)

그래프의 모든 verts를 탐색할 때까지 위의 프로세스를 계속진행

# BFS의 sudo code BFS(graph, startVert): for v of graph.vertexes: v.color = white startVert.color = gray queue.enqueue(startVert)# 시작 while !queue.isEmpty(): u = queue[0] # 큐의 헤드 (S) # 이웃문을 체크하는 것이 핵심부분 for v of u.neighbors: if v.color == white: v.color = gray queue.enqueue(v) queue.dequeue()# 끝 u.color = black

BFS는 큐 자료구조를 활용하지만, 재귀호출은 사용하지않는다 노드가 적은경우 최단경로를 탐색할때 유용하다 너비우선적으로 노드를 탐색할때, 큐를 활용하므로 노드가 많아지면 메모리저장공간이 증가하는 단점이있다 BFS는 재귀적으로 동작하지않는 이유는-> 인접한 노드에대해 먼저 탐색을 하기 때문에 재귀적으로 재호출할 필요가 없다

Depth-first search 깊이우선탐색

스택의 개념이 사용된다(LIFO)

일단 한방향으로 leaf노드까지 쭉탐색(깊이를 들어간다) -> 그오른쪽 리프탐색 순서 이때 하나의 리프노드에서 바로옆의 리프노드로 갈때 재귀함수를 사용 이 재귀의 개념의 활용이 너비우선탐색과 다른점이다

탐색하기전에 가능한 그래프를 분할하고, 다른경로를 역추적한다 분할한다는것은 깊이별로 탐색을 진행하기 때문에, 내부적으로 그래프가 분할된 후 탐색을 진행하는것이다

주로 모든노드를 방문하는경우 사용되지만, 최단경로를 찾지못하고, 시간이 오래걸릴 수 있다

즉, 찾는 노드의 depth가 깊을수록 빠르고, 메모리를 적게차지한다

DFS 활용 가중 그래프의 최소 스패닝 트리 찾기 길 찾기 그래프에서주기 감지 미로 문제

첫 번째 함수인 DFS()는 그래프를 매개 변수로 사용하고 모든 verts를 방문하지 않음(white)으로 표시한다

각 vert의 부모를 null로 설정한다

이 함수의 다음 루프는 그래프의 각 vert를 방문한다

방문하지 않은 경우, 해당 vert를 두 번째 함수 DFS_visit( )에 전달한다

각 vert의 부모를 null로 설정한다 이 함수의 다음 루프는 그래프의 각 vert를 방문한다 방문하지 않은 경우, 해당 vert를 두 번째 함수 DFS_visit( )에 전달한다 두 번째 함수인 DFS_visit()는 vert를 gray로 표시하여 시작한다(탐색 과정에서)

그런 다음 방문하지 않은 모든 노드(인접노드)의 갯수만큼 반복문을 수행한다

이 루프에서 부모를 설정한 다음 DFS_visit()를 재귀적으로 호출한다

모든 이웃 탐색이 완료되면 vert를 black(방문함)으로 표시한다

DFS(graph):#초기상태 for v of graph.verts: v.color = white v.parent = null for v of graph.verts: if v.color == white: DFS_visit(v) DFS_visit(v): v.color = gray for neighbor of v.adjacent_nodes: if neighbor.color == white: neighbor.parent = v #트리, 그래프 -> 부모개념없다 DFS_visit(neighbor) ## 역추적 v.color = black

from http://bong7233.tistory.com/31 by ccl(A) rewrite - 2021-09-30 13:26:34