DFS와 BFS - 파이썬 구현

https://unsplash.com/photos/iAlerP-CnBY

DFS, BFS에 대해 알아보자

 

 

 

 

 

---

얻어갈 지식

• DFS, BFS

 

 

 

 

 

DFS( Depth-First Search : 깊이 우선 탐색)

깊이 우선 탐색 ( DFS )

깊이 우선 탐색은 그래프에서 한 루트로 더 이상 내려갈 곳이 없을 때까지 검색한 뒤 옆으로 이동하여 다른 루트를 검색하는 방식이다.

 

보통 한없이 깊이 검색하는 것을 방지하기 위해 깊이 제한을 사용한다.

 

깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 가장 최근 노드의 부모 노드로 되돌아와서, 이전과는 다른 노드를 선택한다. 여기서 부모 노드로 되돌아오는 과정을 백트리킹이라 한다.

 

장점

단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

 

목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 미리 지정한 임의의 깊이까지만 탐색하고 그때까지 목표 노드를 발견하지 못하면 다음 경로를 탐색하는 방법을 사용한다.

 

얻어진 해가 최단 경로라는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해가 최적이 아닐 수 있다는 것이다.

 

구현 ( python3 )

def DFS(graph, index):
	visited = []
	stack = [index]
    
    while stack:
    	r = stack.pop()
        
        if r not in visited:
        	visited.append(r)
            stack.extend(graph[r])
            
def DFS_r(graph, index, visited):
	if index not in visited:
    	visitied.append(index)
        
        for item in graph[index]:
        	DFS_r(graph, item, visited)

 

 

 

 

 

BFS( Breadth-First Search : 깊이 우선 탐색)

너비 우선 탐색( BFS )

너비 우선 탐색은 시작 정점을 방문한 뒤 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 반복한다.

 

장점

출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

단점

경로가 매우 긴 경우 탐색 가지가 급격히 증가함에 따라 많은 기억 공간을 필요로 하게 된다.

 

구현 ( python3 )

from collections import deque

def BFS(graph, index):
	deq = deque()
    deq.append(index)
    visited = []
    
    while deq:
    	r = deq.popleft()
        
        if r not in visited:
        	visited.append(r)
            deq.extedns(graph[r])

 

 

 

 

 

---

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

https://www.youtube.com/watch?v=_hxFgg7TLZQ