Algorithm) DFS/BFS

그래프 탐색 알고리즘: DFS/BFS

탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 그래프 탐색 알고리즘으로 DFS/BFS가 존재

 

자료구조

스택(선입후출)

먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조

예시) 박스 쌓기

 

DFS method 정의 

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 = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9
dfs(graph, 1, visited)

 

BFS method 정의 

간선 비용이 모두 같을 때 최단거리를 탐색하기 위해 쓰일 수 있는 알고리즘

from collections import deque

# BFS 메서드 정의 
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 = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9
bfs(graph, 1, visited)