def bfs(graph, start):
visited = []
queue = [start]
while queue:
n = queue.pop(0)
if n not in visited:
visited.append(n)
queue += graph[n] - set(visited)
return visited
활용 예시
그래프 내 사이클 확인
두 정점 사이의 Path 찾기
하나의 해를 가진 미로 탈출과 같은 퍼즐 풀기
웹 크롤러
2. 깊이 우선 탐색 DFS
현재 정점에서 갈 수 있는 만큼 최대한 깊이 가고, 더 갈 곳이 없다면 이전 정점으로 돌아가는 방식이다. 스택을 이용하거나, 재귀호출을 통해 구현한다. 여기서 한 노드에서 제일 마지막까지 탐색을 마치고 다시 돌아오는 과정을 백트래킹이라고 한다.
def dfs(graph, v, visited):
# 현재 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 인접 노드들 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
활용 예시
최단 경로 구하기
최소 스패닝 트리 구하기
GPS 네비게이션 시스템 : 현재 위치에서의 모든 이웃 location 찾기
Garbage Collection
2️⃣ 최단 경로 알고리즘
그래프에서 가장 짧은 경로를 찾는 알고리즘으로 상황에 맞는 효율적인 알고리즘들이 정립되어 있다.
1. 다익스트라 Dijkstra 알고리즘
다익스트라는 한 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 비교적 빠르게 최단 경로 탐색 가능하다. 음의 간선이 없을 때만 동작하는데 현실 세계는 음의 간선으로 표현되지 않아 실제 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.
그리디 알고리즘으로 분류되며 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택하는 과정을 반복한다. 이 때 힙자료구조를 사용해 시간을 단축할 수 있다. (BFS 큐 + 최소 힙)
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
# 입력받기
n, m = map(int, input().split()) # 노드의 개수, 간선의 개수
start = int(input()) # 시작 노드 번호
distance = [INF] * (n + 1) # 최단 거리 테이블 초기화
# 그래프 (인접 리스트)
graph = [[] for i in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정한 후 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
INF = int(1e9)
# 입력 받기
n, m = map(int, input().split()) # 노드의 개수, 간선의 개수
# 그래프 (배열) 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
graph[a][a] = 0
# 그래프 입력 받기
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c # a -> b 비용은 c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
import sys
input = sys.stdin.readline
INF = int(1e9)
# 입력 받기
v, e = map(int, input().split()) # 노드의 개수, 간선의 개수
distance = [INF] * (v + 1) # 최단 거리 테이블 초기화
# 그래프 (인접 리스트) 입력 받기
edges = []
for _ in range(e):
a, b, c = map(int, input().split())
edges.append((a, b, c)) # (a -> b 의 비용이 c)
def bellman_ford(start):
distance[start] = 0 # 시작 노드 초기화
# 전체 v - 1번의 라운드(round)를 반복
for i in range(v):
# 매 반복마다 '모든 간선'을 확인
for j in range(e):
cur_node, next_node, edge_cost = edges[j]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
distance[next_node] = distance[cur_node] + edge_cost
# v번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == v - 1:
return True
return False
# 벨만 포드 알고리즘 수행
negative_cycle = bellman_ford(1)
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x) :
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 찾기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드 개수와 간선 개수 입력 받기
v, e = map(int, input().split())
# 부모 테이블을 자기 자신으로 초기화
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
# union 연산 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# FIND 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면 루트 노드 찾을 때까지 재귀적으로 호출
if parent[x] != x :
parent[x] = find_parent(parent, parent[x])
return parent[x]
# UNION 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 입력 받기
v, e = map(int, input().split()) # 노드 개수, 간선 개수
# 그래프 (인접 리스트)
edges = []
for _ in range(e):
a, b, c = map(int, input().split())
edges.append((cost, a, b))
edges.sort() # 간선 비용순으로 정렬
# 부모 테이블 초기화
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
result = 0
# 간선 하나씩 확인하면서
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
2) 프림 Prim 알고리즘
프림 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕에 둔다. 즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택한다.
import heapq
from collections import defaultdict
input = sys.stdin.readline
n, m = map(int,input().split()) # 노드 수, 간선 수
visited = [0] * (n+1) # 노드의 방문 정보
# 그래프 (인접 리스트) 입력 받기
graph = defaultdict(list)
for i in range(m):
u, v, weight = map(int,input().split())
graph[u].append([weight, u, v])
graph[v].append([weight, v, u])
# 프림 알고리즘
def prim(graph, start_node):
visited[start_node] = 1 # 방문 갱신
candidate = graph[start_node] # 인접 간선 추출
heapq.heapify(candidate) # 우선순위 큐 생성
mst = [] # mst
total_weight = 0 # 전체 가중치
while candidate:
weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
if visited[v] == 0: # 방문하지 않았다면
visited[v] = 1 # 방문 갱신
mst.append((u,v)) # mst 삽입
total_weight += weight # 전체 가중치 갱신
# 다음 인접 간선 탐색
for edge in graph[v]:
if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입
return total_weight
print(prim(graph,1))
