알고리즘(4) - BFS(Breadth First Search) & DFS(Depth First Search)

DFS(Depth First Search)

그래프의 모든 노드를 탐색하는 방법 중 하나, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 알고리즘. 이 과정에서 재귀 함수를 사용한다. 
# 스택 자료 구조에 기초한다

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')

BFS(Breadth First Search)

DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인전합 노드부터 탐색하는 알고리즘.
#큐 자료구조에 기초한다

출처

https://c4u-rdav.tistory.com/27?category=1082802