[알고리즘] BFS, DFS

그래프(Graph)

그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 객체 간의 관계를 표현하는 데 사용된다.

 

그래프는 다양한 형태로 표현될 수 있으며, 일반적으로 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 구현된다.

 

인접 행렬(Adjacency Matrix)

• 인접 행렬은 2차원 배열로 그래프를 표현하는 방식이다.
• 그래프의 노드 수를 N이라고 할 때, N x N 크기의 행렬을 생성하고, 각 행렬 요소에 노드 간의 연결 여부를 저장한다.
• 인접 행렬은 노드 간의 연결 여부를 상수 시간(O(1))에 확인할 수 있어서 빠른 검색이 필요한 경우 유용하다. 하지만 그래프의 크기가 크면 공간 효율성이 떨어질 수 있다.

 

인접 리스트(Adjacency List)

• 인접 리스트는 각 노드마다 연결된 노드를 리스트로 저장하는 방식이다.
• 그래프의 노드 수를 N이라고 할 때, 길이가 N인 리스트 배열을 생성하고, 각 리스트에는 해당 노드와 연결된 노드를 저장한다.
• 인접 리스트는 그래프의 크기에 비례하여 공간을 사용하며, 노드의 연결 관계를 효율적으로 표현할 수 있다. 그러나 노드 간의 연결 여부를 확인하기 위해서는 리스트를 순회해야 하므로 검색 속도는 인접 행렬보다 느릴 수 있다.

 

예시 코드

# 인접 리스트로 표현한 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}
"""
   A
  / \
 B   C
 |   |
 D   E
"""

 

 

DFS(Depth-Frist Search;깊이 우선 탐색)

깊이 우선 탐색은 트리나 그래프의 노드를 탐색할 때 한 방향으로 계속해서 탐색하다가 더 이상 갈 곳이 없으면 다시 돌아와 다음 경로를 탐색하는 방식의 알고리즘이다.

 

루트에서 시작하여 가장 깊은 곳까지 탐색한 후, 갈 곳이 없으면 이전 노드로 돌아가서 다른 경로로 탐색을 진행한다.

DFS는 재귀 함수 또는 스택(Stack) 자료구조를 사용하여 구현할 수 있다. 재귀 함수를 사용하는 경우 함수 호출의 스택을 이용하여 탐색 경로를 저장하고, 스택을 사용하는 경우 직접 스택에 노드를 저장하고 꺼내어 사용한다.

 

예시코드

# BFS
# 재귀 사용
def dfs(node:str, visited=set())->None:
    visited.add(node)
    print(node, end=' ')

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

print("DFS:")
dfs('A')

 

 

BFS(Breadth-First Search;너비 우선 탐색)

너비 우선 탐색은 루트 노드에서 시작하여 같은 레벨에 있는 노드들을 먼저 탐색한 후, 다음 레벨의 노드로 넘어가며 탐색하는 알고리즘이다.

 

레벨 순서대로 노드를 탐색하므로 가까운 노드부터 방문하게 된다.

BFS의 구현에는 큐(Queue) 자료구조를 사용한다. 큐를 이용하여 방문할 노드를 저장하고, 탐색 과정에서 큐에서 노드를 꺼내어 방문한다.

 

예시코드

# DFS
from collections import deque

def bfs(start_node:str)->None:
    visited = set()
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')

            for neighbor in graph[node]:
                queue.append(neighbor)

print("BFS:")
bfs('A')