[알고리즘/Python] 복습 5. DFS/BFS

DFS

참고한 블로그

Depth First Search의 약자로, 그래프 자료에서 데이터를 탐색하는 알고리즘

데이터를 위에서 아래로 찾는 방식을 DFS라고 부른다(위에서 아래로 탐색할 때 왼쪽으로 가는지 오른쪽으로 가는지는 전혀 상관 없다)

 

DFS 기본 원칙

방문하지 않은 노드만 방문해야한다. 이미 방문한 노드는 다시 방문하지 않는다.

 

구현

• 스택을 이용
  • 성능면에서 떨어지는 단점이 있음

def dfs(graph, start_node):

## 기본은 항상 두개의 리스트를 별도로 관리해주는 것
need_visited, visited = list(), list()

## 시작 노드를 시정하기
need_visited.append(start_node)

## 만약 아직도 방문이 필요한 노드가 있다면,
while need_visited:

    ## 그 중에서 가장 마지막 데이터를 추출 (스택 구조의 활용)
    node = need_visited.pop()

    ## 만약 그 노드가 방문한 목록에 없다면
    if node not in visited:

        ## 방문한 목록에 추가하기
        visited.append(node)

        ## 그 노드에 연결된 노드를
        need_visited.extend(graph[node])

return visited

 

• 재귀함수를 이용
  • 스택을 이용한 것보다 비교적 단순한 구조

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐 
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

BFS

참고한 블로그

 

Breadth First Search의 약자로, 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘

이 특징 때문에 FIFO 방식의 큐 자료구조를 활용한다. 즉 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘을 작성하면 된다.

 

기본 원칙

방문한 노드는 방문처리해서 중복해서 탐색하지 않게 한다.

 

언제 사용?

그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있다

 

BFS 동작과정

1. 탐색 시작 노드 정보를 큐에 삽입하고, 방문처리한다
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문처리한다
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다

# deque 라이브러리 불러오기
from collections import deque

# BFS 메서드 정의
def bfs (graph, node, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([node])
    # 현재 노드를 방문 처리
    visited[node] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True