BFS와DFS 알고리즘

BFS 알고리즘이란 너비 우선 탐색이라고 부르며 그래프에서 가장 가까운 노드부터 탐색해 점점 거리를 벌려가는 알고리즘이다.

이 알고리즘을 사용하기위해 Queue를 사용한다. Queue는 FIFO구조이기 때문에 이 구조를 이용하여 알고리즘을 만들면 BFS의 시작점이 중간에 있으면 노드의 방문을 그려보면 동심원으로 이루어지게 된다.

BFS 알고리즘 순서

DFS 알고리즘은 BFS 알고리즘을 그대로 Queue가 아닌 스택으로 사용하여 구현한 알고리즘이다.

아쉬운점은 처음 시작점에서 DFS 순서대로 이동하면 시작점에서 이동한 거리가 비례해서 증가하지 않는다는 것이다.

DFS 알고리즘 순서

이렇게 BFS와 DFS가 어떤 방식으로 구현되는지 알아보았고, 이 알고리즘을 코드로 써본다면 아래와 같은 코드가 될 것이다.

from collections import deque

def bfs (graph, node, visited):
    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
                
def dfs(graph, start_node):
    visited = []
    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
graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)
print()
print(dfs(graph, 1))