DFS vs. BFS

Depth First Search (DFS): Searches from the root to the deepest node of the tree first
Breadth First Search (BFS): Searches the first depth of the nodes before moving on to the next depth

DFS using recursion

1. 루트 노드부터 시작한다.
2. 현재 방문한 노드를 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 2부터 반복한다.

graph = {
    # Root node is 1
    # Nodes on the first level
    1: [2, 5, 9],
    # Node connected to 2
    2: [1, 3],
    # Node connected to 3
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

visited = []
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    # 루트 노드부터 시작
    visited_array.append(cur_node)

    for adjacent_node in adjacent_graph[cur_node]:
        # If the adjacent node is not visited
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)

    return visited_array

DFS using stack

Stack is used as pop returns the last node in an array that allows to search the depth first.

1. 루트 노드를 스택에 넣습니다.
2. 현재 스택의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2부터 반복한다.
5. 스택이 비면 탐색을 종료한다.

def dfs_stack(adjacent_graph, start_node):
    visited = []
    stack = [start_node]

    # While stack is not empty
    while stack:
        # Put visited node in from stack to visited array
        curNode = stack.pop()
        visited.append(curNode)

        # Check a node in stack
        for adjNode in adjacent_graph[curNode]:
            # If the adjacent node is not in the visited array
            if adjNode not in visited:
                # Append the adjacent node if not visited
                stack.append(adjNode)
    return visited

BFS using queue

Queue is used as dequeue returns the first node in an array that allows to evaluate the entire level first.

1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가딕 비면 탐색을 종료한다.

def bfs_queue(adj_graph, start_node):
    visited = []
    queue = [start_node]

    # While queue is not empty
    while queue:
        # Dequeue visited node in from queue to visited array
        curNode = queue[0]
        queue.remove(curNode)
        visited.append(curNode)

        # Check a node in queue
        for adjNode in adj_graph[curNode]:
            # If the adjacent node is not in the visited array
            if adjNode not in visited:
                # Append the adjacent node if not visited
                queue.append(adjNode)
    return visited