PYTHON_알고리즘_BFS, DFS

깊이 우선 탐색(DFS)

• 보통 모든 노드를 방문하고자 할 경우에 사용
• BFS보다 속도가 느리다.

from collections import deque
def dfs(graph,start,n):
    need_visited, visited = deque([start]),deque()
    while need_visited:
        node = need_visited.pop()
        if node not in visited:
            visited.append(node)
            need_visited.extend(reversed(graph[node]))
    return visited

너비 우선 탐색(BFS)

• 보통 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 사용

from collections import deque
def bfs(graph,start,n):
    need_visited, visited = deque([start]),deque()
    while need_visited:
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])

    return visited