DFS란?

DFS(Depth First Search) 즉 깊이 우선 탐색이다.
구현방법에는 2가지 방식이 있다 스택과 재귀함수로 구현하는 방법이 있다.

DFS 파이썬으로 구현

스택

#visited 배열 생성
# stack 배열 start넣어서 생성
# stack이 없을때까지 반복
# stack에서 pop으로 top값 가져옴
# 방문배열에 추가
# 그래프[노드]갯수만큼 요소반복
# 그때 그노드는 방문한적 없어야함
# 조건 충족시 스택에 추가
#dfs와 bfs의 차이는 visited를 for문에서 추가해주냐(bfs) 노드로 추가해주냐(dfs)

def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

재귀함수

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

BFS란?

BFS(Breadth-First Search) 너비 우선 탐색이다.
즉 인접 노드 부터 찾는 방식이다.
구현방법에는 큐로 구현하는 방법이 있다.

BFS 파이썬으로 구현

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}
#방문한 배열 stat넣고 생성
# deque start넣고 생성
#q가 없을때까지 반복
# q에서 popleft로 node를 가져옴
# 그래프[노드] 갯수만큼 반복
# 그때 그노드는 방문한적이 없어야함(방문한 배열로 확인)
# 조건 충족시 q랑 방문한 배열에 추가
# 이렇게 해야지 q에 방문 한적 없는 아이들만 추가 되고 방문한 적없는 노드에서 돌면서 노드를 찾음

#dfs와 bfs의 차이는 visited를 for문에서 추가해주냐(bfs) 노드로 추가해주냐(dfs)
def bfs_queue(start):
    visited = [start]
    q = deque([start])
    # q가 탐색할 친구
    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited

이미지 출처:
https://velog.io/@still3028/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-DFS-BFS