[알고리즘] BFS(너비우선탐색), DFS(깊이우선탐색) 1

Hyo Kyun Lee·2022년 1월 13일
0

알고리즘

목록 보기
10/45

9. BFS

너비우선탐색, data 탐색을 할 때 너비를 기준(특정노드에 인접해있는 모든 노드들을 탐색대상으로 설정)으로 탐색을 하는 탐색방법의 일종이다.

최단거리탐색 및 미로찾기 등 경로탐색에 사용할 수 있으며, Queue 자료구조를 이용하면, 자료구조의 특징을 이용하여 BFS를 구현할 수 있다.

위 graph에서

  • 최초 node인 1을 queue에 넣는다.
  • 1은 방문하였으므로 방문배열에 넣고, 인접노드인 2와 3을 queue에 넣는다.
  • 2를 방문한 후 방문배열에 넣고, 1의 인접노드인 4,5를 queue에 넣는다.
  • 이 과정을 반복한다.

queue 자료구조에 따라 다음 탐색대상은 3이고, 그 후에 2의 인접노드들이 탐색대상이 된다.

9-1. 파이썬

graph 상태를 표현하는 방법은 여러가지가 있는데, 본 방법에서는 객체내에서 key값과 인접노드를 연결하는 방식으로 구현하였다.

from queue import Queue

graph = {
    1: [2,3],
    2: [1,3,4,5],
    3: [1,2,6,7],
    4: [2,5],
    5: [2,4],
    6: [3,7],
    7: [3,6]
}

def bfs(graph, start):
    checked = []
    q = Queue()
    q.put(start)

    while q.qsize() > 0:
        node = q.get()
        if node not in checked:
            checked.append(node)
            for adj in graph[node]:
                q.put(adj)
    return checked


print(bfs(graph, 1))

10. DFS

깊이우선탐색, data 탐색을 할 때 깊이를 기준(특정노드에 인접해있는 노드, 해당 노드에 인접해있는 노드 즉 노드가 연결되어있는 깊이 및 수준을 계층적으로 탐색)으로 탐색하는 방법의 일종이다.

stack 자료구조를 사용하여 구현할 수 있다.

10-1. 파이썬

graph = {
    1: [2,3],
    2: [1,3,4,5],
    3: [1,2,6,7],
    4: [2,5],
    5: [2,4],
    6: [3,7],
    7: [3,6]
}

def bfs(graph, start):
    checked = []
    stack =[]
    stack.append(start)

    while stack :
        node = stack.pop()
        if node not in checked:
            checked.append(node)
            for adj in graph[node]:
                stack.append(adj)
    return checked


print(bfs(graph, 1))

참조링크

graph structure
https://www.section.io/engineering-education/graph-data-structure-python/

bfs, dfs
https://ebbnflow.tistory.com/234

DFS/BFS
https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16

0개의 댓글