그래프 순차 탐색 알고리즘
두 알고리즘은 그래프의 구조와 목적에 따라 적절하게 선택해서 사용할 수 있습니다. DFS는 노드의 깊은 부분을 빠르게 탐색하고자 할 때 유용하며, BFS는 시작 노드로부터 가까운 노드를 먼저 방문하고자 할 때 유용합니다.
깊이 우선 탐색 (DFS)
깊이 우선 탐색은 시작 노드에서 시작하여 하나의 노드를 선택하고 그 노드의 인접 노드로 이동하는 방식입니다. 이를 재귀적으로 반복하면서 더 이상 방문할 노드가 없을 때까지 진행합니다.
- 시간 복잡도: O(V + E), ( V : 노드의 수, E : 간선의 수)
- 공간 복잡도: O(V) (스택이나 재귀 호출을 위한 공간)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
visited = set()
def dfs(graph, node):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbour in graph[node]:
dfs(graph, neighbour)
dfs(graph, 'A') # Output: A B D E C F너비 우선 탐색 (BFS)
너비 우선 탐색은 시작 노드에서 시작하여 그 노드의 모든 인접 노드를 먼저 방문한 후, 이웃의 이웃을 방문하는 방식으로 진행됩니다.
- 시간 복잡도: O(V + E), ( V : 노드의 수, E : 간선의 수)
- 공간 복잡도: O(V) (큐를 위한 공간)
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(graph[node])
bfs(graph, 'A') # Output: A B C D E F최단 경로 탐색 알고리즘
한 정점에서 다른 정점까지의 최단 경로를 탐색합니다.
다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 가중치가 있는 그래프에서 시작점부터 다른 모든 정점까지의 최단 거리를 찾는 알고리즘입니다.
- 시간 복잡도: O(V log V + E log V) (우선순위 큐 사용 시)
- 공간 복잡도: O(V + E)
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A')) # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드 알고리즘은 다익스트라 알고리즘과 비슷한 목적을 가지지만, 음의 가중치를 가진 간선이 있는 그래프에서도 작동합니다.
- 시간 복잡도: O(V * E)
- 공간 복잡도: O(V)
def bellman_ford(graph, start):
distance = {node: float('infinity') for node in graph}
distance[start] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbour, weight in graph[node].items():
if distance[node] + weight < distance[neighbour]:
distance[neighbour] = distance[node] + weight
# Check for negative weight cycles
for node in graph:
for neighbour, weight in graph[node].items():
if distance[node] + weight < distance[neighbour]:
print("Graph contains a negative weight cycle")
return
return distance
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(bellman_ford(graph, 'A')) # Output: {'A': 0, 'B': 1, 'C': 3, 'D': 4}Minimum Spanning Tree 탐색 알고리즘
- Minimum Spanning Tree(MST, 최소 신장 트리) : 그래프의 모든 노드를 포함하면서 가중치의 합이 최소가 되는 트리
프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 그래프의 모든 노드를 포함하면서 가중치의 합이 최소가 되는 트리, 즉 최소 신장 트리를 찾는 알고리즘입니다.
- 시간 복잡도: O(V^2) (인접 행렬), O(E + V \log V) (우선순위 큐와 인접 리스트 사용 시)
- 공간 복잡도: O(V + E)
import heapq
def prim(graph, start):
mst = []
visited = set()
edges = [(0, start, start)]
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, cost))
for to_next, cost in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost, to, to_next))
return mst
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(prim(graph, 'A')) # Output: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 1)]크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘도 프림 알고리즘과 같이 최소 신장 트리를 찾습니다. 하지만 이 알고리즘은 간선을 가중치 기준으로 정렬한 뒤, 가장 가중치가 작은 간선부터 추가하는 방식으로 동작합니다.
- 시간 복잡도: O(E log E) (간선을 정렬하는 데에 대부분의 시간이 소요)
- 공간 복잡도: O(V + E)
def find_parent(parents, node):
if parents[node] == node:
return node
return find_parent(parents, parents[node])
def union(parents, a, b):
root_a = find_parent(parents, a)
root_b = find_parent(parents, b)
if root_a != root_b:
parents[root_a] = root_b
def kruskal(graph):
mst = []
edges = []
for node in graph:
for neighbour, weight in graph[node].items():
edges.append((weight, node, neighbour))
edges.sort()
parents = {node: node for node in graph}
for edge in edges:
weight, frm, to = edge
if find_parent(parents, frm) != find_parent(parents, to):
mst.append((frm, to, weight))
union(parents, frm, to)
return mst
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(kruskal(graph)) # Output: [('A', 'B', 1), ('C', 'D', 1), ('B', 'C', 2)]그 외 알고리즘
플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘은 그래프의 모든 노드 쌍 사이의 최단 경로를 찾는 알고리즘입니다.
- 시간 복잡도: O(V^3)
- 공간 복잡도: O(V^2)
def floyd_warshall(graph):
dist = {}
for node in graph:
dist[node] = {neighbor: float('inf') for neighbor in graph}
dist[node][node] = 0
for node in graph:
for neighbor, weight in graph[node].items():
dist[node][neighbor] = weight
for k in graph:
for i in graph:
for j in graph:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(floyd_warshall(graph))A* (A-star) 탐색 알고리즘
A* 알고리즘은 휴리스틱 함수를 사용하여 경로 탐색에 있어 더 효율적인 결과를 내는 알고리즘입니다. 주로 게임에서 경로 찾기 등에 사용됩니다.
- 시간 복잡도: O(E) (휴리스틱 함수와 구현 방법에 따라 다르지만, 일반적으로 O(E))
- 공간 복잡도: O(V)
import heapq
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_star(graph, start, goal):
frontier = [(0, start)]
came_from = {start: None}
cost_so_far = {start: 0}
while frontier:
_, current = heapq.heappop(frontier)
if current == goal:
break
for neighbor in graph[current]:
new_cost = cost_so_far[current] + graph[current][neighbor]
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heuristic(goal, neighbor)
heapq.heappush(frontier, (priority, neighbor))
came_from[neighbor] = current
# Reconstruct path
current = goal
path = []
while current != start:
path.append(current)
current = came_from[current]
path.append(start)
path.reverse()
return path, cost_so_far[goal]
graph = {
(0, 0): {(0, 1): 1, (1, 0): 1.5},
(0, 1): {(0, 0): 1, (1, 1): 1},
(1, 0): {(1, 1): 1, (0, 0): 1.5},
(1, 1): {(1, 0): 1, (0, 1): 1}
}
print(a_star(graph, (0, 0), (1, 1))) # Output: ([(0, 0), (0, 1), (1, 1)], 2)
공부!