DFS와 BFS

DFS(Depth First Search)

DFS는 노드와 간선으로 이루어진 그래프에서 깊이를 우선으로 탐색하는 알고리즘 기법으로, 재귀함수와 해시테이블을 통해 구현할 수 있습니다.

만약 노드가 1~6까지 있고 간선이 다음과 같이 존재한다고 하면,

해시테이블은 다음과 같이 구현됩니다 :

이때 visitied 배열 혹은 집합을 제작하여 중복된 방문을 방지합니다.

DFS를 실행하면, dfs(1)일 때, 1 → 6 → 3 → 4 → 5 → 2 순으로 탐색합니다.

DFS 구현

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
table = {}
visited = []

for _ in range(m):
    x, y = map(int, input().split())
    if x not in table:
        table.update({x: [y]})
    else:
        table[x].append(y)

def dfs(node):
    visited.append(node)

    if node in table:
        for neighbor in table[node]:
            if neighbor not in visited:
                dfs(neighbor)

dfs(1)
print(*visited, sep=' -> ')

BFS(Breadth First Search)

BFS는 노드와 간선으로 이루어진 그래프에서 너비를 우선으로 탐색하는 알고리즘 기법으로, 큐와 해쉬테이블을 통해 구현할 수 있습니다.

위와 같은 해시테이블과 visited 배열을 통해 구현하면 다음과 같습니다. 이때 bfs(1)은 1 → 6 → 3 → 2 → 4 → 5 입니다.

BFS 구현

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
table = {}
visited = []

for _ in range(m):
    x, y = map(int, input().split())
    if x not in table:
        table.update({x: [y]})
    else:
        table[x].append(y)

def bfs(start):
    queue = deque([start])
    visited.append(start)

    while queue:
        node = queue.popleft()
        if node in table:
            for neighbor in table[node]:
                if neighbor not in visited:
                    visited.append(neighbor)
                    queue.append(neighbor)

bfs(1)
print(*visited, sep=' -> ')

DFS와 BFS(BOJ 1260)

import sys
from collections import deque

input = sys.stdin.readline
n, m, k = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
table = {}
visited_dfs = []
visited_bfs = []

for _ in range(m):
    x, y = map(int, input().split())
    if x not in table:
        table.update({x: [y]})
    else:
        table[x].append(y)
    if y not in table:
        table.update({y: [x]})
    else:
        table[y].append(x)
for i in range(1, n+1):
    if i in table:
        table[i].sort()

def dfs(node):
    visited_dfs.append(node)

    if node in table:
        for neighbor in table[node]:
            if neighbor not in visited_dfs:
                dfs(neighbor)

def bfs(start):
    queue = deque([start])
    visited_bfs.append(start)

    while queue:
        node = queue.popleft()
        if node in table:
            for neighbor in table[node]:
                if neighbor not in visited_bfs:
                    visited_bfs.append(neighbor)
                    queue.append(neighbor)

dfs(k)
bfs(k)

print(*visited_dfs)
print(*visited_bfs)