[알고리즘-이론] DFS/BFS

Jinga·2023년 4월 3일

BFS DFS 알고리즘 이론

알고리즘-이론

목록 보기

4/5

DFS(깊이우선탐색)

Depth first search의 약자로 그래프 자료에서 데이터를 탐색하는 알고리즘이다.
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

위의 그래프와 같이 더 이상 찾아내려갈 수 없을 때 까지 깊게 탐색하는 알고리즘이다.

DFS 구현

DFS는 항상 앞으로 찾아 가야 할 노드와 이미 방문한 노드를 기준으로 탐색한다.
즉 특정 노드가 앞으로 찾아 가야 할 노드라면 계속 탐색을 해 나가는 것이고, 이미 방문한 노드라면 무시하거나 따로 저장하면 된다.

아래의 코드는 위의 그래프 사진을 딕셔너리로 표현한 것이다.

graph = dict() 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

deque를 활용 한 DFS구현

def dfs(graph, start_node):
# 방문한 노드를 담을 리스트
visited = []    
# 방문해야 할 노드를 담을 deque
need_visited = deque()
#시작 노드 설정해주기
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
print(dfs(graph, 'A')) =>  ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']
        재귀함수를 이용한 DFS구현
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
visited = []

        재귀함수를 이용한 DFS구현2
def dfs(graph, v, visited):    
    #v는 시작위치
    visited[v] = True
    print(v , end = ' ')    
    #현재 노드와 연결된 노드를 재귀적으로 호출
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)    
graph = [
    [],
    [2,3,7],
    [1,4,6],
    [1,5, 7],
    [2,6],
    [3,7],
    [2,4],
    [1,3]
]
#각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False] * 9
dfs(graph, 1, visited) => 1 2 4 6 3 5 7

BFS(Breadth First Search/ 너비 우선 탐색)

BFS란

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
시작 정점에 가까이 있는 정점부터 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문 하는 순회 방법이다.
즉, DFS와는 다르게 넓게 탐색하는 방법이다.

BFS의 특징

DFS와는 다르게 재귀적을 동작하지 않는다.
어떤 노드를 방문했었는지에 대한 여부를 반드시 검사해야 한다.
이를 검사하지 않을 시 무한루프에 빠질 수 있다.
선입선출(FIFO)를 원칙으로 탐색하며 deque를 사용하여 구현할 수 있다.

BFS의 탐색 과정

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

BFS 소스코드 예제(Python)

    from collections import deque
    # BFS 함수 정의
    def bfs(graph, start, visited):
        # 큐(Queue) 구현을 위해 deque 라이브러리 사용
        queue = deque([start])
        # 현재 노드를 방문 처리
        visited[start] = True
        # 큐가 빌 때까지 반복
        while queue:
            # 큐에서 하나의 원소를 뽑아 출력
            v = queue.popleft()
            print(v, end=' ')
            # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
    # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
    graph = [
      [],
      [2, 3, 8],
      [1, 7],
      [1, 4, 5],
      [3, 5],
      [3, 4],
      [7],
      [2, 6, 8],
      [1, 7]
    ]
    # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
    visited = [False] * 9
    # 정의된 BFS 함수 호출
    bfs(graph, 1, visited)