[자료구조,알고리즘] - DFS, BFS

...

---

DFS(Depth-First Search)

◾ 정의

깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 스택 자료구조(혹은 재귀함수)를 이용한다.

◾ 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리합니다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

재귀를 통해 구현

def dfs(graph, node, visited):
    print(node, visited)
    visited[node] = True

    for neighbor in graph[node]:
        if visited[neighbor] == False:
            dfs(graph, neighbor, visited)

dfs(graph, 1, visited)

스택을 통한 구현 방법도 있지만 재귀를 사용하면 코드의 가독성을 높인다.

BFS(Breadth-First Search)

◾ 정의

BFS는 너비 우선 탐색이라고도 부르며, 그래프에 시작 노드로부터 가까운 노드부터 우선적으로 탐색하는 알고리즘으로 큐 자료구조를 이용한다.

◾ 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

◾ 적용하는 곳

• 최단거리/경로 계산

  인접 노드를 우선으로 탐색하기 때문에 목적지와 가까운 노드를 순차적으로 탐색한다.