깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)

 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 가 있다.

 

❓그래프는 

링크 추가 예정

 

1. 깊이 우선 탐색(DFS, Depth-First Search)

출처 : https://yuanie.tistory.com/9

• 루트 노드 혹은 임의의 한 노드에서 시작하여 연결된 노드의 끝까지 탐색을 진행한 후 다음 노드로 넘어가는 것을 말한다.
• 가장 마지막에 들어온 값들이 먼저 나가는 LIFO(Last In First Out) 스 구조를 가진다.
• 모든 노드를 방문하고자 할 경우 선택한다.
• 구현 자체는 간단하지만 너비 우선 탐색(BFS) 보다는 느리다.

 

def DFS(graph):
    visited = [False] * len(graph)
    visited[0] = True
    stack = graph[0]
    answer = [1]
    while stack:
        next_step = stack.pop()-1
        if not visited[next_step]:
            stack.extend(graph[next_step])
            visited[next_step] = True
            answer.append(next_step+1)
    return answer

graph = [
    [4, 3, 2],
    [7, 6, 5, 1],
    [1],
    [11, 1],
    [2],
    [9, 2],
    [10, 2],
    [],
    [6],
    [7],
    [4],
]

print(DFS(graph))
# [1, 2, 5, 6, 9, 7, 10, 3, 4, 11]

 

• 위 그림의 코드를 구현해 뒀다. 코드는 방식이 다양해서 내가 만든 코드가 꼭 정답이란 법은 없다. 여기서는 그림과 같게 나오기 위해서 그래프 값들을 내림차순 정렬을 진행해뒀으며 실제로는 오름차순에서도 뽑을 순 있다.
• 1번 노드와 연결된 노드들을 모두 넣고, 각 노드별 연결된 노드들을 모두 대칭되게 넣어줬다.

 

2. 너비 우선 탐색(BFS, Breadth-First Search)

출처 : https://yuanie.tistory.com/9

• 루트 혹은 임의의 한 노드에서 시작하여 인접한 노드들을 순서대로 방문하는 탐색 방법
• 두 노드 사이의 최단거리를 찾는 문제에서 유용하게 사용 된다.
• 먼저 들어온 노드의 순서대로 방문하기 때문에 FIFO(First In First Out)  방식으로 구성된다.

 

def BFS(graph):
    visited = [False] * len(graph)
    visited[0] = True
    stack = graph[0]
    answer = [1]
    while stack:
        next_step = stack.pop(0)-1
        if not visited[next_step]:
            stack.extend(graph[next_step])
            visited[next_step] = True
            answer.append(next_step+1)
    return answer

graph = [
    [2, 3, 4],
    [1, 5, 6, 7],
    [1],
    [1, 11],
    [2],
    [2, 9],
    [2, 10],
    [],
    [6],
    [7],
    [4],
]

print(BFS(graph))

 

3. DFS와 BFS의 차이

	DFS	BFS
장점	- 현 경로상 노드들만 기억하기 떄문에 적은 메모리 사용 (낮은 공간 복잡도) - 목표 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 탐색 가능	- 모든 경로를 탐색하기에 여러 해가 있을 경우 최단 경로임을 보장 - 최단 경로가 존재하면 깊이가 무한하더라도 답을 찾을 수 있다. - 노드 수가 적고, 깊이가 얕은 해가 존재할 떄 유리
단점	- 해가 없는 경로 탐색시 끝날 떄까지 탐색 - 잘못된 경로가 깊으면 빠지게 됨 - 목표에 이르는 경로가 다수인 경우, DFS는 해에 도착하면 탐색을 종료하기 전 얻어진 해가 최적이라는 보장이 없다.	- 노드 수가 많을수록 탐색 가지가 급격히 증가함에 따라 많은 메모리를 필요 - 메모리 상 확장된 노드를 저장할 필요가 있기에 탐색하는 트리 or 그래프의 크기에 비례하는 공간 복잡도를 가