[Python] 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)

2024. 12. 6. 14:46·BackEnd/Python
반응형
DFS (Depth-First Search)


깊이 우선 탐색은 한 경로를 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다. 

스택 자료구조나 재귀를 사용하여 구현됩니다.

 

DFS는 모든 경로를 탐색하므로 그래프의 깊이가 깊을 경우 적합합니다.

 

예시 코드

 

def dfs(graph, start):
    visited = set()  # 방문한 노드 집합
    route = []  # 탐색 경로
    stack = [start]  # 스택에 시작 노드 추가

    while stack:
        vertex = stack.pop()  # 스택의 맨 위 노드를 꺼냄
        if vertex not in visited:
            route.append(vertex)  # 경로에 추가
            visited.add(vertex)  # 방문 처리
            stack.extend(reversed(graph[vertex]))  # 인접 노드 스택에 추가 (LIFO 구조)
    return route

# 예제 그래프
graph = {
    0: [1, 2, 4],
    1: [0, 3],
    2: [0],
    3: [1, 5],
    4: [0],
    5: [3]
}

# DFS 수행
result = dfs(graph, 0)
print("DFS 결과:", result)

 

결과 예시

 

  0 - 1 - 3 - 5
   \   \
    2   4

 

 


1. 스택: [0], 방문: {}, 경로: []

 

2. 스택: [], 방문: {0}, 경로: [0]

인접 노드 [4, 2, 1] 추가 → 스택: [4, 2, 1]

 

3. 스택: [4, 2], 방문: {0, 1}, 경로: [0, 1]
인접 노드 [3] 추가 → 스택: [4, 2, 3]

 

반복하여 모든 노드를 방문

 

최종 결과: [0, 1, 3, 5, 2, 4]

 

BFS (Breadth-First Search)

 

너비 우선 탐색은 시작 정점에서 가까운 노드부터 탐색을 확장해 나가는 방식입니다.

큐 자료구조를 사용하여 구현됩니다.

 

BFS는 그래프의 최단 경로를 탐색하거나 계층 구조를 파악하는 데 적합합니다.

 

예시 코드

 

def bfs(graph, start):
    visited = set()  # 방문한 노드 집합
    route = []  # 탐색 경로
    queue = [start]  # 큐에 시작 노드 추가

    visited.add(start)  # 방문 처리
    while queue:
        vertex = queue.pop(0)  # 큐의 맨 앞 노드 제거
        route.append(vertex)  # 경로에 추가

        # 인접 노드 방문
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return route

# BFS 수행
result = bfs(graph, 0)
print("BFS 결과:", result)

 

BFS 수행 과정

 

1. 큐: [0], 방문: {}, 경로: []
2. 큐: [1, 2, 4], 방문: {0}, 경로: [0]
3. 큐: [2, 4, 3], 방문: {0, 1}, 경로: [0, 1]

 

반복하여 모든 노드를 방문

 

최종 결과: [0, 1, 2, 4, 3, 5]

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'BackEnd > Python' 카테고리의 다른 글

[Python] 선형 탐색(Linear Search) 이진 탐색 (Binary Search)  (0) 2024.12.07
[Python] 해시 테이블 (Hash Table)  (0) 2024.12.02
[Python] 우선순위 큐와 힙 (Priority Queue & Heap)  (0) 2024.12.02
[Python] 스택, 큐, 데크  (0) 2024.11.27
[Python] 한 번에 여러 개 입력(input) 받기  (0) 2024.11.15
'BackEnd/Python' 카테고리의 다른 글
  • [Python] 선형 탐색(Linear Search) 이진 탐색 (Binary Search)
  • [Python] 해시 테이블 (Hash Table)
  • [Python] 우선순위 큐와 힙 (Priority Queue & Heap)
  • [Python] 스택, 큐, 데크
Dev Chu
Dev Chu
  • Dev Chu
    Log_Double 7
    Dev Chu
  • 전체
    오늘
    어제
    • LOG LIST (201) N
      • log Double 7 (2)
        • notice (1)
        • 회고록 (1)
      • Study (112) N
        • 과제 (2)
        • 코딩 테스트 (105)
        • 대규모 시스템 설계 기초 (5) N
      • CS (10)
        • 자료구조 & 알고리즘 (4)
        • Design Pattern (2)
        • TIL (4)
      • FrontEnd (26)
        • HTML & CSS (16)
        • JavaScript & jQuery (9)
        • React (1)
      • BackEnd (24)
        • Java (4)
        • Python (6)
        • Database (0)
        • Spring (6)
      • Infra & DevOps (3)
        • AWS (3)
        • Git (8)
      • Project (4) N
        • repo_bis (2)
        • WhiteMonday (2) N
      • ETC (20)
        • TIP (13)
        • Error (5)
        • SQLD (2)
  • 블로그 메뉴

    • 코딩 테스트
  • 링크

    • GitHub
  • 공지사항

    • Log Double 7
  • 인기 글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Dev Chu
[Python] 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)
상단으로

티스토리툴바