DFS

DFS (Depth First Search)

DFS는 방문한 노드의 인접노드 그 인접노드의 인접노드를 타고 들어가서 더이상 방문하지 않은 인접노드가 없을때까지 연쇄적으로 반복하는 방식으로 그래프를 순회하기 때문에 stack 또는
재귀함수로 구현한다. 재귀함수로 구현하는 경우가 Stack으로 구현하는 방식에 비해 코드가 간결하지만 재귀 콜스택이 많이 쌓이게 되어 함수 호출 스택의 최대 용량을 초과하는 경우가 발생할 수 있으므로 주의해야한다.

Stack을 이용한 DFS 구현

def dfs(_graph, _start_node):
    visited, stack = [], []

    # push start node to stack
    stack.append(_start_node)

    while stack:
        current_node = stack.pop()

        # if current node is already visited, end turn and go to first part of while loop
        if current_node in visited:
            continue

        # else current node is not in visited list, add to visited list and check adjacent nodes
        visited.append(current_node)
        for adjacent_node in _graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)

    return visited

BFS

BFS(Breadth First Search)

BFS는 시작노드로부터 가까운 노드들을 우선적으로 방문하는 알고리즘이다.
시작 노드로부터 거리가 1인 노드들을 먼저 방문하고 이후 거리가 2인 노드, 3인 노드.. 와 같은 순서대로 방문하는 식이다. BFS는 주로 queue를 이용하여 구현한다.

Queue를 이용한 BFS 구현

# 번호가 낮은 인접 노드부터 방문한다고 가정
def bfs(_graph, _start_node):

    queue, visited = [], []

    # 시작 노드를 queue에 넣고 시작한다.
    queue.append(_start_node)

    while queue:

        temp = []
        current_node = queue.pop(0) # left pop for using list data structure as queue
        if current_node in visited:
            continue

        visited.append(current_node)


        for adjacent_node in _graph[current_node]:
            if adjacent_node not in visited:
                temp.append(adjacent_node)
		
        # 인접 노드의 번호가 낮은 순서대로 방문하기 위해서 Sort. 
        temp.sort()
        queue += temp
        visited.extend(temp)

    return visited