DFS & BFS
BFS와 DFS 정리
BFS (너비 우선 탐색)
탐색 순서만 구할 때
목적: 그래프의 모든 노드를 방문하거나, 특정 노드를 찾고자 할 때.
특징: 시작 노드에서 가까운 노드부터 차례대로 방문합니다. 큐(Queue)를 사용하여 구현하며, 레벨별로 탐색합니다.
구현:
from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)
거리나 최단 경로를 구할 때
목적: 시작 노드로부터 다른 노드까지의 최단 거리나 경로를 알고 싶을 때.
특징: BFS의 특성상, 먼저 방문된 노드까지의 경로가 최단 경로가 됩니다. 거리를 추적하기 위해 배열이나 딕셔너리를 추가적으로 사용합니다.
구현:
from collections import deque def bfs_with_distances(graph, start): distances = {node: -1 for node in graph} distances[start] = 0 queue = deque([start]) while queue: vertex = queue.popleft() for neighbor in graph[vertex]: if distances[neighbor] == -1: distances[neighbor] = distances[vertex] + 1 queue.append(neighbor) return distances
DFS (깊이 우선 탐색)
경로 탐색 및 순서 확인
목적: 그래프에서 특정 경로를 찾거나, 노드를 깊이 우선으로 탐색하여 순서를 확인하고자 할 때.
특징: 가능한 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색합니다. 재귀 호출 또는 명시적인 스택(Stack)을 사용해 구현할 수 있습니다.
구현:
def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=' ') for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited)
특정 구조 탐색 및 분석
목적: 그래프의 특정 구조나 속성을 분석하고자 할 때. 예를 들어, 사이클이 있는지 확인하거나, 강한 연결 요소(SCC)를 찾는 등의 작업.
특징: 재귀적으로 그래프를 탐색하며, 특정 조건을 만족하는지 검사합니다. DFS의 깊이 우선 특성을 활용하여 복잡한 그래프 구조를 탐색할 수 있습니다.
구현 (사이클 탐지 예시):
def dfs_cycle_detection(graph, node, visited, parent): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: if dfs_cycle_detection(graph, neighbor, visited, node): return True elif parent != neighbor: return True return False
요약
BFS:
- 탐색 순서: 큐를 사용해 레벨별로 노드를 방문
- 최단 경로: 거리 배열을 사용해 최단 경로 계산
DFS:
- 경로 탐색: 깊이 우선으로 재귀적으로 노드를 방문
- 구조 분석: 사이클 탐지, 강한 연결 요소 찾기 등에 활용
BFS와 DFS 정리 표
아래는 BFS와 DFS의 주요 목적과 특징을 표로 정리한 내용입니다. 이 표를 통해 각 알고리즘의 사용 목적과 구현 방법을 한눈에 확인할 수 있습니다.
| 알고리즘 | 사용 목적 | 주요 특징 | 구현 방식 |
|---|---|---|---|
| BFS | 탐색 순서만 구할 때 | - 큐(Queue)를 사용하여 레벨별로 노드를 방문 | deque를 이용한 큐 구현 |
| - 가까운 노드부터 차례로 탐색 | |||
| 거리나 최단 경로를 구할 때 | - 거리 배열을 사용하여 각 노드까지의 최단 거리를 계산 | deque + 거리 배열(distances) |
|
| - 방문된 경로가 최단 경로가 됨 | |||
| DFS | 경로 탐색 및 순서 확인 | - 재귀 호출 또는 스택(Stack)을 사용하여 깊이 우선 탐색 | 재귀 함수 구현 |
| - 가능한 깊이까지 들어간 후, 다시 돌아와 다른 경로 탐색 | |||
| 특정 구조 탐색 및 분석 | - 그래프의 구조적 특성 분석 (예: 사이클 탐지, SCC) | 재귀 함수 + 특정 조건 검사 (if문 활용) |
|
| - 재귀적으로 그래프의 각 경로를 탐색하며 구조 분석 |
요약
- BFS:
- 탐색 순서: 가까운 노드부터 차례로 방문.
- 최단 경로: 거리 배열로 최단 거리 계산.
- DFS:
- 경로 탐색: 깊이 우선으로 노드를 방문.
- 구조 분석: 사이클 탐지, 강한 연결 요소 분석 등에 사용.
인접리스트
1. 양방향 그래프 (Undirected Graph)
def initialize_undirected_graph(N):
"""N개의 노드를 가진 양방향 그래프 초기화"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_edge(graph, u, v):
"""양방향 간선 추가"""
graph[u].append(v)
graph[v].append(u)
# 사용 예시
N = 5
graph = initialize_undirected_graph(N)
add_edge(graph, 1, 2)
add_edge(graph, 1, 3)
add_edge(graph, 4, 5)
print(graph)2. 단방향 그래프 (Directed Graph)
def initialize_directed_graph(N):
"""N개의 노드를 가진 단방향 그래프 초기화"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_directed_edge(graph, u, v):
"""단방향 간선 추가"""
graph[u].append(v)
# 사용 예시
N = 5
graph = initialize_directed_graph(N)
add_directed_edge(graph, 1, 2)
add_directed_edge(graph, 1, 3)
add_directed_edge(graph, 4, 5)
print(graph)3. 가중 그래프 (Weighted Graph)
def initialize_weighted_graph(N):
"""N개의 노드를 가진 가중 그래프 초기화"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_weighted_edge(graph, u, v, weight):
"""가중치가 있는 양방향 간선 추가"""
graph[u].append((v, weight))
graph[v].append((u, weight))
# 사용 예시
N = 5
graph = initialize_weighted_graph(N)
add_weighted_edge(graph, 1, 2, 5)
add_weighted_edge(graph, 1, 3, 10)
add_weighted_edge(graph, 4, 5, 3)
print(graph)4. 자기 자신과의 연결 허용 (Self-loop)
def initialize_self_loop_graph(N):
"""N개의 노드를 가진 그래프 초기화 (자기 자신과의 연결 허용)"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_self_loop(graph, u):
"""자기 자신과의 연결 추가"""
graph[u].append(u)
# 사용 예시
N = 5
graph = initialize_self_loop_graph(N)
add_self_loop(graph, 1)
print(graph)5. 멀티그래프 (Multigraph)
def initialize_multigraph(N):
"""N개의 노드를 가진 멀티그래프 초기화"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_multiple_edges(graph, u, v, count):
"""동일한 두 노드 간 여러 간선 추가"""
for _ in range(count):
graph[u].append(v)
graph[v].append(u)
# 사용 예시
N = 5
graph = initialize_multigraph(N)
add_multiple_edges(graph, 1, 2, 3)
print(graph)6. 비연결 그래프 (Disconnected Graph)
def initialize_disconnected_graph(N):
"""N개의 노드를 가진 그래프 초기화 (비연결 상태 허용)"""
graph = {i: [] for i in range(1, N + 1)}
return graph
def add_edge(graph, u, v):
"""양방향 간선 추가"""
graph[u].append(v)
graph[v].append(u)
# 사용 예시
N = 5
graph = initialize_disconnected_graph(N)
add_edge(graph, 1, 2) # 1번과 2번 연결
# 3번, 4번, 5번 노드는 연결되지 않음
print(graph)요약
- 양방향 그래프: 가장 많이 사용하는 기본적인 그래프 유형.
- 단방향 그래프: 특정 방향으로만 이동할 수 있는 경우에 사용.
- 가중 그래프: 간선에 가중치가 있는 그래프, 최단 경로 문제에 자주 사용.
- 자기 자신과의 연결: 노드가 자기 자신으로 연결되는 경우를 허용.
- 멀티그래프: 동일한 두 노드 간 여러 간선이 존재할 수 있는 그래프.
- 비연결 그래프: 일부 노드들이 서로 연결되지 않은 상태를 표현.
'배움 __IL > 자료구조&알고리즘' 카테고리의 다른 글
| Hash Table 정리 (0) | 2024.02.19 |
|---|---|
| 알고리즘 3줄 정리 [DP : Memoization, ] (1) | 2023.12.28 |
| 알고리즘 3줄 정리 [합병정렬, 퀵정렬] (0) | 2023.12.26 |
| 동적계획법 : 동적계획법 이론과 문제 (0) | 2023.04.02 |
| 그리디 : 그리디 알고리즘 이론과 문제 (0) | 2023.04.02 |