DFS

DFS는 깊이 우선 탐색 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상확에서 최대한 깊숙이 들어가서 노드를 방문한후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

DFS는 스택 자료구조를 이용하며 동작 과정:
1.탐색 시작 노드를 스택에 삽입하고 방문처리
2.스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
3 2번과정을 더 이상 수행할 수 없을 때까지 반복한다.

과정

DFS코드 구현

def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=",")
    # 현재 노드와 연결된 다른 노그를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


graph = [
    [1, 2],
    [0, 3, 4, 5],
    [0, 6],
    [1],
    [1],
    [1],
    [2]
]

visited = [False]*9

dfs(graph, 0, visited)

결과

0,1,3,4,5,2,6,

BFS

Bfs 는 너비우선탐색 알고리즘이다 가까운 노드부터 탐색하는 알고리즘이다.
Dfs 는 최대한 더 멀리있는것 부터 먼저 탐색하는데 bfs 는 그 반대다.

알고리즘의 정확한 동작은
1.탐색 시작 노드를 큐에 삽입하고 방문처리한다
2.큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두
큐에 삽입시킨다 그리고 방문처리한다.
3.2번 과정을 더이상 큐에서 꺼낼게 없을 때까지 수행한다.

너비 우선 탐색알고리즘은 deque라이브러리 이용함으로써 큐 자료구조를 이용해서 구현이 간단하게 사용된다. 수행시간은 O(N) 의 시간이 소요된다.일반적으로 실제 수행시간이 DFS 보다 좋은편이다 이것은 아직 제대로된 지식이없기때문에 ㅎㅎ 나중에 알게되면 다시 정리를 한번 해보겠다.지금은 일단 bfs가 dfs 보다 수행시간이 더 짧다는것만 기억하자.

과정

1.먼저 0을 큐에 삽입하고 0은빠지고 1과2를 큐에 삽입한다.

2.1이 빠지고 3과4가 큐에 삽입한다 이때 큐 상황은: [2,3,4]

3.2가 큐에서 빠지고 5와6이 삽입된다 큐 상황은: [3,4,5,6]

4.나머지는 근접 노드가 없기때문에 차례대로 빠져나온다 .

탐색순서는 다음과 같다 0,1,2,3,4,5,6

BFS코드 구현

from collections import deque


def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


graph = [
    [1, 2],
    [0, 3, 4],
    [0, 5, 6],
    [1],
    [1],
    [2],
    [2]
]

visited = [False]*9

bfs(graph, 0, visited)

결과

0 1 2 3 4 5 6

정리

DFS:동작원리는 스택을 사용해서 동작하고 구현방법은 재귀함수를 이용하면된다
BFS:동작원리는 큐를 사용하고 구현방법은 큐 자료구조를 이용해서 구현하면된다