/
/

[알고리즘/Python] BFS & DFS

알고리즘PythonBFSDFS
avatar
유댕이
2025.03.21
·
6 min read

인접 행렬 (Adjacency Matrix)

  • 2차원 배열로 그래프의 연결 관계를 표현하는 방식

  • 탐색할 때

    • 모든 노드를 확인해야 하므로 시간복잡도는 O(N^2)이다.

    • 행렬 인덱스를 이용해 빠르게 접근 가능하므로, graph[i][j] 조회는 O(1)이다.

  • 노드 개수가 적고 간선이 많을 때 활용

(0) --- (1)
  \   
   \   
    (2)
graph = [
    [0, 1, 1],  # 0번 노드 → 1번, 2번과 연결
    [1, 0, 0],  # 1번 노드 → 0번과 연결
    [1, 0, 0]   # 2번 노드 → 0번과 연결
]

인접 리스트 (Adjacency List)

  • 연결된 노드만 리스트로 저장하는 방식

    • 메모리를 효율적으로 사용 가능

  • 노드를 문자열로 나타냈을 때, 딕셔너리를 활용할 수 있다.

  • 탐색할 때,

    • graph[i]에 연결된 노드만 순회하면 되므로, 연결된 간선 수에 비례하여 O(V+E)

  • 노드 개수가 많고 간선이 적을 때 활용

graph = {
    0: [1, 2],  # 0번 노드는 1번, 2번과 연결
    1: [0],     # 1번 노드는 0번과 연결
    2: [0]      # 2번 노드는 0번과 연결
}
4229

BFS

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

    • 가까운 노드부터 탐색하는 알고리즘

    • 인접한 모든 정점들을 방문하고, 방문한 정점들과 연결된 모든 정점들을 방문하는 것을 반복하는 탐색 방법

  • 큐 자료구조 활용

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

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

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

인접 행렬 + 큐

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for neighbor, connected in enumerate(graph[node]): # 인접 행렬 탐색 -> 각 노드의 연결 여부(0/1)를 확인해야 함
            if connected and not visited[neighbor]: # 연결된 노드만 탐색
                visited[neighbor] = True
                queue.append(neighbor)

인접 리스트 + 큐

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:  # 인접 리스트는 바로 접근 가능
            if not visited[neighbor]:
                visited[i] = True
                queue.append(neighbor)

DFS

  • 깊이 우선 탐색 (Depth-First Search)

    • 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

  • 스택 자료구조 및 재귀함수 활용

    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

    2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 만약 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

인접 행렬 + 재귀함수

def dfs(graph, node, visited):
    visited[node] = True

    for neighbor, connected in enumerate(graph[node]): # 모든 노드 탐색 (행렬)
        if connected and not visited[neighbor]: # 연결된 노드 중 방문하지 않은 노드 찾기
            dfs(graph, neighbor, visitied)

인접 리스트 + 재귀함수

# 재귀 활용
def dfs_recursive(graph, node, visited):
    visited[node] = True # (1) 방문한 정점 기록

    for neighbor in graph[node]: # (2) 해당 정점이 갈 수 있는 경로 지정
                       # (3) 다음 정점이 이미 방문한 곳이라면 방문하지 않음
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited) # (4) 방문하지 않았다면 다음 정점을 인자로 넘김
    return visited # (5) 더이상 방문할 정점이 없으면 return 반환

인접 행렬 + 스택

def dfs(graph, start, visited):
    stack = [start]
    visited[start] = True

    while stack:
        node = stack.pop()
        for neighbor, connected in enumerate(graph[node]):
            if connected and not visited[neighbor]:
                visted[neighbor] = True
                stack.append[neighbor]

인접 리스트 + 스택

# 스택 자료구조 활용
def dfs_stack(v):
    visited = set() # 이전에 방문한 노드 저장
    stack = [v] # 방문할 노드를 저장

    while stack: # 스택이 비어있을 때까지 탐색
        node = stack.pop() # 스택에서 가장 최근에 추가된 노드 가져옴

        if node not in visited: # 해당 정점이 아직 방문하지 않았다면
            visited.add(node) # 방문한 노드를 visited 집합에 저장

            for next_node in graph[node]: # 다음 정점들을 스택에 추가
                if next_node not in visited:
                    stack.append(next_node) # 다음에 방문할 노드를 스택에 추가
     return visited

- 컬렉션 아티클