[Python] DFS, BFS

DFS (깊이 우선 탐색)은 연결된 끝 노드까지 찾아가면서 탐색한다. 스택구조로 구현한다. (선입후출)

def dfs(graph, v, visited):
	visitied[v] = True
	for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

인자는 그래프, 현재 위치, 방문기록 리스트를 전달한다. 현재 위치를 방문처리하고, 그래프 (인접리스트)에서 방문하지 않은 곳이 있다면 그 노드에 대해서 DFS를 재귀함수 형식으로 불러온다. DFS는 덩어리 나누기, 지역 나누기와 같은 문제에 좋다.

 

BFS (너비 우선 탐색)은 인접한 노드부터 탐색한다. 큐 구조로 구현한다. (선입선출)

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
            v = queue.popleft()
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                visited[i] = True

먼저, python에서 큐를 사용하기 위해 deque 모듈을 사용한다. 그래프와 시작점, 방문기록 리스트를 인자로 전달한다. 큐에 시작점을 넣고, 큐가 비어있지 않은 동안 큐에서 노드를 꺼내 해당 노드에서 방문하지 않은 노드를 큐에 넣으면서 탐색한다.