DFS, BFS

DFS와 BFS는 그래프를 탐색하는 방법이다

 

그럼 그래프란??

 

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 순서대로 모든 정점들을 한 번씩 방문하는 것

 

node : 위치를 뜻함, 정점

 

edge : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함, Link or Branch

 

무방향 그래프 : 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음

 

방향 그래프 : 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 있음

 

가중치 그래프(네트워크) : 간선에 비용 또는 가중치가 할당된 그래프

 

싸이클 : 단순 경로의 시작 노드와 종로 노드가 동일한 경우

 

비순환 그래프 : 싸이클이 없는 그래프

 

완전 그래프 : 그래프의 모든 노드가 서로 연결되어 있는 그래프

 

그래프 표현

- 파이썬에서 제공하는 딕셔너리와 리스트 자료구조를 활용하여 표현 가능

- 각 node를 key로 한 뒤, 해당 node들을 리스트 만들어 value로 추가

 

graph = dict()
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
print(graph)

 

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)

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2,3,8], # 1번 노드와 연결
    [1,7], # 2번 노드와 연결
    [1,4,5], # ...
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)


# 실행 결과
1 2 7 6 8 3 4 5

 

BFS

너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 큐 자료구조를 이용한다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    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

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

# 실행 결과
1 2 3 8 7 4 5 6

 

dfs와 bfs의 차이