[Algorithm] DFS, BFS

그래프 탐색

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요
• 두 가지 방법
  • 깊이 우선 탐색 (Depth First Search, DFS)
  • 너비 우선 탐색 (Breadth First Search, BFS)

 

DFS (깊이우선탐색)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,
  가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여
  결국 모든 정점을 방문하는 순회방법
• 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

 

DFS 알고리즘

1. 시작 정점 v를 결정하여 반문
2. 정점 v에 인접한 정점 중에서
   1. 방문하지 않는 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w 방문, 그리고 w를 v로 하여 다시 반복
   2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 반복
3. 스택이 공백이 될 때까지 2를 반복

'''
7 8   : 노드 수, 간선 수
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7   : 간선간의 연결
'''

def dfs(v):
    stack = []
    stack.append(v)

    while stack:
        v = stack.pop() # 현재 방문하려는 노드

        if visited[v] == 0:
            visited[v] = 1     # 방문 표기
            print(v, end=' ')  # 현재 방문한 노드 출력

            for w in range(1, V+1):  # 인접 노드 순회
                if G[v][w] == 1 and visited[w] == 0:
                    stack.append(w)

V, E = 7, 8
temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]

G = [[0 for _ in range(V+1)] for _ in range(V+1)]
visited = [0 for _ in range(V+1)]

for i in range(0, len(temp)-1, 2):
    G[temp[i]][temp[i+1]] = 1
    G[temp[i+1]][temp[i]] = 1

# 인접 행렬 확인
# for i in range(V+1):
#     print('{} | {}'.format(i, adj[i]))

dfs(1)

• 재귀 이용

def dfs(v):
    visited[v] = 1
    print(v, end=' ')

    for w in range(1, V+1):
        if G[v][w] == 1 and visited[w] == 0:
            dfs(w)

 

BFS (너비 우선 탐색)

• 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에,
  방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접 정점에 대해 탐색한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용

 

BFS 알고리즘

from collections import deque

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    
    visited = [[0]*N for _ in range(N)]
    visited[i][j] = 1

    dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]

    while queue:
        x, y = queue.popleft()

        for dx, dy in dxy:
            nx, ny = x+dx, y+dy

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
            	visited[nx][ny] = 1
                queue.append((nx, ny))

 

https://clementmihailescu.github.io/Pathfinding-Visualizer/

Pathfinding Visualizer