파이썬의 그래프
그래프 관계(relationship)을 표현하는 자료 구조로, 파이썬에서는 어떤 관계를 표현할때 적합한 것은 사전(dictionary)이다. 그래프는 인접 행렬, 인접 리스트로도 나타낼 수 있다.
키(key) : 노드
값(value) : 키와 연결된 노드 리스트
#무방향 그래프
graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}
#방향 그래프
graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}리스트를 이용하여 그래프를 나타내 보자. 리스트의 인덱스가 사전의 key에 해당하고, 인덱스의 값은 사전의 값과 똑같다.
#무방향 그래프
graph1 = [[], [2, 3, 5], [1, 3], [1, 2, 4], [3, 5], [1, 4]]
#방향 그래프
graph2 = [[], [2, 3], [3], [4], []. [1, 4]]그래프의 깊이우선탐색
전위 순회는 부모를 먼저 방문한 후에 왼쪽, 오른쪽 자식을 방문한다
이진 트리는 부모에서 자식으로 가는 방향이 있고 모든 노드가 루트 노드에 연결된 그래프이다. 하지만 그래프는 방향이 없을 수 있고, 모든 노드가 특정 노드에 모두 연결되는 것이 아니다.
예로 위의 예시의 무방향 그래프를 노드 1부터 깊이 우선 탐색하는 과정을 들어보자.
- 노드 1을 방문 처리 한다
- 노드 1에 연결된 [2, 3, 5] 중에 아직 방문하지 않은 한 곳을 방문한다. 노드 2 !
- 노드 2에 연결된 노드 [1, 3] 중에 아직 방문하지 않은 노드 3을 방문한다
- 다음 방문할 노드가 이미 방문한 곳인지 확인해야 한다
- visited라는 집합을 만들고, 방문한 노드를 visited에 추가한다
- 어떤 노드를 방문할때마다 visited에 있는 노드인지 확인한다
- 노드 3에 연결된 노드 [1, 2, 4] 중에 아직 방문하지 않은 노드 4를 방문한다
- 마지막으로 노드 5를 방문한다
- 모든 노드 방문 완료로 종료한다
위의 방식은 재귀적으로 구현하거나, 스택으로 구현할 수 있다.
재귀적 DFS
#무방향 그래프
graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}
#방향 그래프
graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}
def dfs_recursive (graph, node):
# 방문 결과를 담을 리스트와 방문 여부를 확인할 집합을 만든다
res = []
visited = set()
#깊이 우선 탐색하는 재귀함수를 만든다
def dfs(u):
#이미 방문한 노드이면 종료한다
if u in visited :
return
#현재 노드를 방문 처리 한다
visited.add(u)
res.append(u)
#현재 노드와 간선으로 연결된 노드들을 깊이 우선 탐색한다
for v in graph[u]:
dfs(v)
dfs(node)
return res
print("무방향 그래프의 깊이 우선 탐색")
print("==========================")
print("노드 1에서 시작: ", dfs_recursive(graph1, 1))
print("노드 2에서 시작: ", dfs_recursive(graph1, 2))
print()
print("방향 그래프의 깊이 우선 탐색")
print("========================")
print("노드 1에서 시작: ", dfs_recursive(graph2, 1))
print("노드 2에서 시작: ", dfs_recursive(graph2, 2))결과값
무방향 그래프의 깊이 우선 탐색
==========================
노드 1에서 시작: [1, 2, 3, 4, 5]
노드 2에서 시작: [2, 1, 3, 4, 5]
방향 그래프의 깊이 우선 탐색
========================
노드 1에서 시작: [1, 2, 3, 4]
노드 2에서 시작: [2, 3, 4]스택의 DFS
이진 트리와 동일하지만, 이미 방문한 노드인지 확인할 집합을 만들고 확인하는 과정이 추가로 필요하다
def dfs_stack(graph, node):
#방문할 노드를 저장한 스택과 방문 여부를 확인한 집합을 만든다
#스택과 집합에 방문할 첫 노드를 넣는다
res = []
stack = [node]
visited = set(stack)
#스택이 빌 때까지 반복한다
while stack :
#스택에서 노드를 꺼내고 방문처리 한다
u = stack.pop()
res.append(u)
#현재 노드에 연결된 다른 노드를 확인한다
#다른 노드가 아직 방문하지 않은 노드라면, 스택과 집합에 넣는다
for v in graph[u]:
if v not in visted:
visited.add(v)
stack.append(v)
return res
print("무방향 그래프의 깊이 우선 탐색")
print("==========================")
print("노드 1에서 시작: ", dfs(graph1, 1))
print("노드 2에서 시작: ", dfs(graph1, 2))
print()
print("방향 그래프의 깊이 우선 탐색")
print("========================")
print("노드 1에서 시작: ", dfs(graph2, 1))
print("노드 2에서 시작: ", dfs(graph2, 2))
결과값
무방향 그래프의 깊이 우선 탐색
==========================
노드 1에서 시작: [1, 5, 4, 3, 2]
노드 2에서 시작: [2, 3, 4, 5, 1]
방향 그래프의 깊이 우선 탐색
========================
노드 1에서 시작: [1, 3, 4, 2]
노드 2에서 시작: [2, 3, 4]재귀적으로 구현한 것과 방문 순서가 다르다! 스택은 후입 선출이라서 나중에 들어간 노드가 먼저 방문 결과에 들어가기 때문에 나오는 결과이다.
무방향 그래프의 스택 탐색 과정은..
- 노드 1을 방문한 후에 노드 1에 연결된 [2, 3, 5]를 순서대로 스택에 넣는다
- 스택에서 노드를 꺼내면 마지막에 들어간 5가 먼저 나온다.
- 노드 1에서 노드 5로 방문한다. …. (생략)
그래프의 너비우선탐색
너비 우선 탐색은 큐를 사용한다. 무방향 그래프를 노드 1부터 너비 우선 탐색을 해보면 다음과 같다.
- 노드 1을 방문처리 하고 큐에 넣는다
- 큐에서 노드 1을 꺼내서 출력한다
- 노드 1에 인접한 노드 2, 3, 5를 방문처리하고 큐에 넣는다
- 큐에서 노드 2를 꺼내서 출력한다. 노드 2에 인접한 1과 3을 방문했으므로 큐에서 노드를 꺼낸다
- 위 과정을 반복하면,
1, 2, 3, 5, 4순으로 출력된다
큐의 BFS
#무방향 그래프
graph1 = {1:[2, 3, 5], 2:[1, 3], 3:[1, 2, 4], 4:[3, 5], 5:[1, 4]}
#방향 그래프
graph2 = {1:[2, 3], 2:[3], 3:[4], 4:[], 5:[1, 4]}
def bfs(graph, node):
#방문 결과를 저장할 리스트와 방문여부를 저장할 집합을 만들고
#가장 처음 방문할 노드를 큐에 넣는다
res = []
queue = [node]
visited = set(queue)
#큐가 빌때까지 반복한다
#큐에서 노드를 꺼내고 방문처리 한다
while queue:
u = queue.pop(0)
res.append(u)
#현재 노드에 연결된 모든 노드를 확인한다
#방문하지 않은 노드라면, 방문처리를 하고 큐에 넣는다
for v in graph[u]:
if v not in visited :
visited.add(v)
queue.append(v)
return res
def bfs (graph, node):
result = []
queue = [node]
visited = set(queue)
while queue :
u = queue.pop(0)
result.append(u)
for v in graph[u]:
if v not in visited:
visited.add(v)
queue.append(v)
return result
print("무방향 그래프의 너비 우선 탐색")
print("==========================")
print("노드 1에서 시작: ", bfs(graph1, 1))
print("노드 2에서 시작: ", bfs(graph1, 2))
print()
print("방향 그래프의 너비 우선 탐색")
print("========================")
print("노드 1에서 시작: ", bfs(graph2, 1))
print("노드 2에서 시작: ", bfs(graph2, 2))결과값
무방향 그래프의 너비 우선 탐색
==========================
노드 1에서 시작: [1, 2, 3, 5, 4]
노드 2에서 시작: [2, 1, 3, 5, 4]
방향 그래프의 너비 우선 탐색
========================
노드 1에서 시작: [1, 2, 3, 4]
노드 2에서 시작: [2, 3, 4]DFS - BFS 함수 비교
다음 그래프에 대한 각각의 깊이 우선 탐색과 너비 우선 탐색을 진행한다
g1 = {1: [2, 3, 4], 2: [1, 5], 3: [1, 6], 4: [1, 6], 5: [2, 6], 6: [3, 4, 5]}
g2 = {1: [3], 2: [3], 3: [5, 6], 4: [6], 5: [], 6: [5]}
def dfs_recursive(graph, node):
result = []
visited = set()
def dfs(u):
if u in visited :
return
visited.add(u)
result.append(u)
for v in graph[u]:
dfs(v)
dfs(node)
return result
def bfs (graph, node):
result = []
queue = [node]
visited = set(queue)
while queue :
u = queue.pop(0)
result.append(u)
for v in graph[u]:
if v not in visited:
visited.add(v)
queue.append(v)
return result
print("무방향 그래프의 탐색 (노드 1에서 시작)")
print("================================")
print("깊이 우선 탐색: ", dfs_recursive(g1, 1))
print("너비 우선 탐색: ", bfs(g1, 1))
print()
print("방향 그래프의 탐색 (노드 1에서 시작)")
print("===============================")
print("깊이 우선 탐색: ", dfs_recursive(g2, 1))
print("너비 우선 탐색: ", bfs(g2, 1))
- DFS와 BFS의 방문순서 디테일 (g1 기준)
- 초기 상태
queue = [1]visited = {1}result = []
- 1 방문 → 인접한
[2, 3, 4]큐에 추가 - →
queue = [2, 3, 4],result = [1] - 2 방문 → 인접한
[1, 5], 1은 이미 방문, 5는 새로 추가 - →
queue = [3, 4, 5],result = [1, 2] - 3 방문 → 인접한
[1, 6], 6은 새로 추가 - →
queue = [4, 5, 6],result = [1, 2, 3] - 4 방문 → 인접한
[1, 6], 모두 방문됨 - →
queue = [5, 6],result = [1, 2, 3, 4] - 5 방문 → 인접한
[2, 6], 이미 방문됨 - →
queue = [6],result = [1, 2, 3, 4, 5] - 6 방문 → 인접한
[3, 4, 5], 이미 방문됨 - →
queue = [],result = [1, 2, 3, 4, 5, 6]
- 초기 상태
- 🔁 BFS 탐색 흐름
### 🔁 DFS 탐색 흐름
1. **초기 상태**
- `visited = set()`
- `result = []`
- 시작 노드: `1`
2. **1 방문** → 인접한 `[2, 3, 4]`, 2부터 재귀 호출
→ `visited = {1}`, `result = [1]`
3. **2 방문** → 인접한 `[1, 5]`, 1은 이미 방문, 5 재귀 호출
→ `visited = {1, 2}`, `result = [1, 2]`
4. **5 방문** → 인접한 `[2, 6]`, 2는 이미 방문, 6 재귀 호출
→ `visited = {1, 2, 5}`, `result = [1, 2, 5]`
5. **6 방문** → 인접한 `[3, 4, 5]`, 5는 이미 방문, 3 재귀 호출
→ `visited = {1, 2, 5, 6}`, `result = [1, 2, 5, 6]`
6. **3 방문** → 인접한 `[1, 6, 4]`, 1, 6은 이미 방문, 4 재귀 호출
→ `visited = {1, 2, 3, 5, 6}`, `result = [1, 2, 5, 6, 3]`
7. **4 방문** → 인접한 `[1, 6]`, 모두 이미 방문됨 → 탐색 종료
→ `visited = {1, 2, 3, 4, 5, 6}`, `result = [1, 2, 5, 6, 3, 4]`이분 그래프
이분 그래프 (Bipartite Graph)란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어 있는 그래프를 이분 그래프라 한다.
이분 그래프의 특징
- 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다
- 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 무조건 같은 색으로 칠해진다
- 연결 성분의 개수 (Connected Component)를 구하는 방법과 유사하다
- 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.
이분 그래프인지 확인하는 방법
서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.
- BFS, DFS 로 탐색하면서 정점을 방문할 때 마다 두 가지 색 중 하나를 칠한다
- 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다
- 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하다면 이분 그래프가 아니다
- BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다. 즉 같은 레벨은 다 같은 색을 가진다
- 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다
이때 주의할 점은 연결 그래프와 비연결 그래프를 둘 다 고려해야 한다. 비연결 그래프는 모든 정점에 대해 확인이 필요하다.
** 연결 그래프 : 모든 정점들이 연결되어있음 / 비연결 그래프 : 그래프 안에 서로 연결되지 않은 정점이 존재함
가중 그래프
각 간선(egde / arc)에 비용 또는 거리 같은 숫자 값이 붙은 그래프
상황별 용도
- 지도, 네비게이션 : 거리 또는 시간
- 네트워크 : 전송 비용, 대역폭
- 게임 : 이동 비용, 에너지 소모
- 추천 시스템 : 연관 강도, 신뢰도
관련 알고리즘
- 다익스트라(Dijkstra) : 음수 가중치 없을 때 최단 경로 (양수일때)
- 벨만 포드 (Bellman-Ford) : 음수 가중치 가능. 음수 사이클 탐지 가능
- 프림(Prim), 크루스칼 (Kruskal) : 최소 신장 트리 (MST) 알고리즘
가중 그래프의 BFS
가중 그래프에서 BFS는 간선의 가중치가 모두 같을때는 ‘최단 거리’를 구할 수 있다. 하지만, 만약 아래와 같이 가중치가 다를 경우에는 부적절하다. 즉, BFS로 찾은 경로가 최단 경로는 아니다.
반대로 DFS는 어떤 노드에 도달할 수 있는가를 탐색하는 알고리즘으로, 가중치의 크기와 상관없이 한 갈래를 끝까지 따라간다. 그래서 가능한 모든 경로를 탐색하거나, 경로의 존재 여부는 알 수 있지만, 최단 거리나 비용 같은 숫자 정보를 고려하고 기록하는데는 부적합하다.
graph = {
"A" : [("B", 1), ("C", 4), ("D", 5)],
"B" : [("A", 1), ("D", 2)],
"C" : [("A", 4), ("D", 4), ("E", 3)],
"D" : [("A", 5), ("B", 2), ("C", 4), ("F", 3)],
"E" : [("C", 3), ("F", 2)],
"F" : [("D", 3), ("E", 2)]
}A → D 의 경로
- 최소 환승 경로 : A → D (소요 시간 = 5)
- 최소 시간 경로 : A → B → D (소요 시간 = 3)
A → F 의 경로
- 최소 환승 경로 : A → D → F (소요 시간 = 8)
- 최소 시간 경로 : A → B → D → F (소요 시간 = 6)
BFS의 경로 찾기 (중간 경로 확인)
BFS 탐색을 통해 각 노드가 어디에서 왔는지를 node_from 딕셔너리에 기록하여 경로를 역추적한다.
#사전을 이용하여 현재 노드가 어떤 노드에서 왔는지 저장한다. 컴프리헨션을 이용하여 사전을 초기화한다.
node_from = {node : "" for node in graph}
def bfs (graph, node):
res = []
queue = [node]
visited = set(queue)
while queue:
u = queue.pop(0)
res.append(u)
for v, w in graph[u] :
if v not in visited :
node_from[v] = u # 현재 노드 v가 노드 u에서 왔다는 것을 기록
visited.add(v)
queue.append(v)
return res
print("탐색 전의 node_from의 상태")
print(node_from)
print()
print("너비 우선 탐색 결과: ", bfs(graph, "A"))
print()
print("탐색 후의 node_from의 상태")
print(node_from)탐색 전의 node_from의 상태
{'A': '', 'B': '', 'C': '', 'D': '', 'E': '', 'F': ''}
너비 우선 탐색 결과: ['A', 'B', 'C', 'D', 'E', 'F']
탐색 후의 node_from의 상태
{'A': '', 'B': 'A', 'C': 'A', 'D': 'A', 'E': 'C', 'F': 'D'}
무방향 그래프의 클래스 만들기
클래스란 ?
데이터(속성)와 동작(메서드)를 하나로 묶는 설계도. “관련된 것들을 하나의 틀로 묶기 위한 도구”
✅ 앞의 가중 그래프에서는 함수로만 했는데, 왜 여기서는 클래스로 묶는것인가?
→ 무방향 그래프는 보통 입력 그래프를 계속 수정하거나, 추가 간선을 양방향으로 처리해야 함
→ 클래스 내부에 add_edge()와 같은 메서드를 만들어서 데이터의 추가+가공을 용이하게 함
→ 반면 가중 그래프 문제에서는 그래프가 고정이라면 딕셔너리와 함수만으로도 충분함
즉, 데이터의 추가 + 가공이 필요할때 클래스를 쓰면 좋다
그래프 클래스에서 구현할 메서드는 다음과 같다
- add_nodes : 그래프에 노드를 추가한다
- add_edges : 그래프에 간선을 추가한다
- delete_nodes : 그래프에서 노드를 삭제한다
- delete_edges : 그래프에서 간선을 삭제한다
- dfs : 그래프를 특정 노드부터 깊이 우선 탐색한다
- bfs : 그래프를 특정 노드부터 너비 우선 탐색한다
- dijkstra : 가중 그래프에서 다익스트라 알고리즘으로 최단 경로를 탐색한다
class Graph :
def __init__(self):
self.graph = {}
self.cost = {} #탐색 비용을 저장
self.node_from = {} #탐색 경로를 저장
#사전을 보기 좋게 출력해주는 pprint 이용
def display(self):
from pprint import pprint
pprint(self.graph)
print()
# *nodes는 가변 인자다
def add_nodes(self, *nodes):
for u in nodes:
#노드가 그래프에 없을 때 추가한다
if u not in self.graph :
self.graph[u] = {}
def add_edges(self, *edges):
for edge in edges:
u, v = edge[0], edge[1]
#간선 정보에 가중치가 없으면 0을 넣ㄴ느다
w = edge[2] if len(edge) == 3 else 0
#노드를 삽입하고, 연결될 노드와 가중치를 입력한다
self.add_nodes(u, v)
#무방향 그래프에서 양쪽 노드가 서로 연결되어 있음을 명시적으로 표현
# u -> v로 가는 간선의 가중치 w // v -> u 로 가는 간선의 가중치 w
self.graph[u][v] = w
self.graph[v][u] = w
#노드와 간선을 삭제할때, 간선 삭제 후 노드 삭제
def delete_edges(self, *edges):
for u, v in edges:
self.graph[u].pop(v, None)
self.graph[v].pop(u, None)
def delete_nodes(self, *nodes):
for u in nodes :
#그래프에 없는 노드이면 스킵
if u not in self.graph:
continue
#먼저 u와 연결된 모든 이웃 노드에서 u를 제거 (간선 제거)
for v in self.graph[u]:
self.graph[v].pop(u, None)
#u 자체를 그래프에서 제거 (노드 삭제)
del self.graph[u]
def dfs (self, node):
result = [] #탐색 순서를 저장할 리스트
visited = set() #방문한 노드를 기록할 집합
#노드별 탐색 비용과, 어디서 왔는지를 저장할 딕셔너리 초기화
self.cost = {node: 0 for node in self.graph}
self.node_from = {node: None for node in self.graph}
def dfs_recur(u):
visited.add(u) #현재 노드 방문 처리
result.append(u) #방문 순서에 추가
#현재 노드 u와 연결된 노드 v를 순회
for v not in self.graph[u] :
if v not in visited : #아직 방문하지 않은 경우
#누적 비용 = 이전 노드까지 비용 + 현재 간선 가중치
self.cost[v] = self.cost[u] + self.graph[u][v]
self.node_from[v] = u #v는 u에서 왔다고 기록
dfs_recur(v) #재귀 호출
dfs_recur(node) #시작 노드부터 탐색 시작
return res #전체 탐색 순서 반환
def bfs (self, node) :
from collections import deque
result = []
queue = deque([node]) #시작 노드를 큐에 넣음
visited = set(queue)
#비용과 노드 정보를 저장하는 사전을 초기화한다
self.cost = {node: 0 for node in self.graph}
self.node_from = {node: None for node in self.graph}
while queue :
u = queue.popleft() #현재 노드 꺼냄
result.append(u) #방문 순서에 추가
for v in self.graph[u]: #인접 노드를 순회
if v not in visited : #방문 처리
visited.add(v)
self.cost[v] = self.cost[u] + self.graph[u][v]
self.node_from[v] = u
queue.append(v) #다음 탐색 대상으로 큐에 삽입
return result
def dijkstra(self, start):
import math, heapq
#각 노드까지의 최소 비용을 무한대로 초기화
self.cost = {node: math.inf for node in self.graph}
self.node_from = {node: None for node in self.graph}
self.cost[start] = 0 #시작 노드는 비용 0
result = [] #탐색한 노드 순서 저장
visited = set() #방문한 노드 저장
heap = [] #우선순위 큐
heapq.heappush(heap, (0, start)) #(비용, 노드) 형태로 삽입
while heap:
prev_time, u = heapq.heappop(heap) #현재까지 가장 비용이 적은 노드 꺼냄
if u in visited:
continue #이미 방문한 노드면 패스
result.append(u)
visited.add(u)
for v in self.graph[u]:
if (new_time := prev_time + self.graph[u][v]) < self.cost[v] :
self.cost[v] = new_time #최소 비용 갱신
self.node_from[v] = u #경로 추적용 정보 저장
heapq.heappush(heap, (self.cost[v], v)) #우선순위 큐에 넣음
return result
def get_path(self, end):
path = ""
node = end
#끝에서 부터 역추적하며 경로 문자열을 만든다
while self.node_from[node]:
path = " -> " + str(node) + path
node = self.node_from[node]
#한 노드에서 다른 노드로 가는 경로가 없을때도 처리
if path :
path = str(node) + path
return f"{path} (cost = {str(self.cost[end])})"
else:
return f"There is no path."
가중그래프의 최단 경로
최단경로 알고리즘 비교표
| 항목 | Dijkstra | Bellman-Ford | Floyd-Warshall |
| 목적 | 단일 시작점 → 모든 노드 최단 경로 | 단일 시작점 → 모든 노드 최단 경로 | 모든 노드 간 최단 경로 |
| 음수 간선 | ❌ 허용 안 됨 | ✅ 허용됨 | ✅ 허용됨 (단, 사이클 감지는 못함) |
| 음수 사이클 | ❌ 감지 불가 | ✅ 감지 가능 | ❌ 감지 불가 |
| 시간 복잡도 | O(E log V) (우선순위 큐 사용 시) | O(V × E) | O(V³) |
| 공간 복잡도 | O(V) or O(V+E) | O(V) | O(V²) |
| 그래프 형태 | 희소 그래프에 적합 | 희소 그래프에 적합 | 정점 수가 적은 Dense 그래프에 적합 |
| 장점 | 빠르고 효율적 | 음수 간선 가능, 간단함 | 전체 쌍 간 경로 한 번에 계산 |
| 단점 | 음수 간선 X | 느리고 비효율적 (큰 입력에서) | 시간/공간 복잡도 큼 |
| 사용 예시 | 네비게이션, 게임 경로 찾기 | 금융 그래프, 손해 계산 | 전 구간 연결 네트워크 비용 계산 |
다익스트라(Dijkstra) 알고리즘
가중 그래프에서 최단 경로를 찾는데 사용된다. 위성 항법 시스템을 이용하여 길 찾을 때도 이 알고리즘을 이용한다고 한다. 위와 같은 예시를 사용하겠다.
이 그래프의 최소 경유지(환승) 경로는 A → D → F 이지만, 최단 경로는 A → B → D → F 이다.
- A에서 D까지 가는 최단 경로는 A → B → D 이다
- A에서 B까지 가는 최단 경로는 A → B 이다
- 즉 구간별로 쪼개서 봐도 모두 최단 경로이다
너비 우선 탐색을 하면서 각 경로로 가는 소요 시간을 기록해두고, 소요 시간을 비교하여 시간이 적게 걸리는 경로를 먼저 탐색하는 것이 다익스트라 알고리즘의 원리이다. 너비 우선 탐색에서는 큐를 사용해, 큐에 넣는 순서대로 경로를 탐색한다. 다익스트라 알고리즘은 큐에 집어넣은 순서에 상관 없이 가중치가 작은것을 먼저 꺼내서 탐색하는 것이 핵심이다.
✅ 다익스트라 알고리즘 자체가 비용이 작은 노드부터 자동으로 처리되게 설계됨. 그래서 최대 비용으로 가려면 다익스트라를 그대로 쓰면 안됨. (큰 가중치를 우선으로 처리하라고 명시해줄 수 없음. 할 수 있어도 최적화된 방법은 아님)
위 내용으로 보면, A → D 까지 가는 경로가 직접 가는 것보다 B를 거쳐 가는 것이 더 빠르기에 시간이 업데이트 되는 점을 중점으로 보면 된다.
다익스트라 알고리즘의 구현
고려 사항
- 너비 우선 탐색과 비슷하게 진행되지만, 큐 대신 우선순위에 따라 꺼내는 자료 구조를 사용해야 한다
- heapq를 이용하여 우선 순위 큐로 구현해보자!
- 방문 처리하는 순서에 유의한다
- bfs와 달리 heapq에서 꺼낸 후에 방문 처리 한다
- 각 노드에 도달하는 데 걸리는 시간을 계산하고 비교하여 시간을 갱신할때 만 힙에 넣는다
#소요 시간을 초기화할때 사용할 무한대(inf)를 이용하기 위해 수학 모듈 사용
import math
import heapq
graph = {
"A": [("B", 1), ("C", 4), ("D", 5)],
"B": [("A", 1), ("D", 2)],
"C": [("A", 4), ("D", 4), ("E", 3)],
"D": [("A", 5), ("B", 2), ("C", 4), ("F", 3)],
"E": [("C", 3), ("F", 2)],
"F": [("D", 3), ("E", 2)]
}
def dijkstra (graph, node) :
#소요시간을 기록할 사전과 현재 노드의 이전 노드를 기록할 사전을 초기화
lead_time = {node : math.inf for node in graph}
node_from = {node : None of node in graph}
#출발 노드의 소요시간을 0으로 만든다
lead_time[node] = 0
visited = set()
#(소요시간, 노드)의 자료를 넣는 최소 힙을 만든다
#출발 노드를 힙에 넣는다
heap = []
heapq.heappush(heap, (0, node))
#힙이 빌 때까지 반복한다
while heap :
#힙에서 자료를 꺼내서 시간과 노드를 변수에 저장한다
prev_time, u = heapq.heappop(heap)
#이미 방문한 노드이면 다음 노드를 꺼내고, 그렇지 않으면 방문처리 한다
if u in visied :
continue
visited.add(u)
#현재 노드에 인접한 노드와 가중치 (소요 시간)을 가져와서 반복한다
for v, weight in graph[u]:
#인접한 노드로 가는 소요시간을 계산하여 기본 값보다 작으면
#시간 정보를 갱신하고, 이전 노드를 기록한다. 그리고 힙에 넣는다
if (new_time := prev_time + weight) < lead_time[v]:
lead_time[v] = new_time
node_from[v] = u
heapq.heappush(heap, (lead_time[v], v))
#소요시간과 이전 노드를 기록한 사전을 반환한다
return lead_time, node_from
lead_time, node_from = dijkstra(graph, "A")
print(node_from)
print(lead_time)
node_from :{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'C', 'F': 'D'}
lead_time :{'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 7, 'F': 6}위 코드 중 if u in visited 내용을 삭제해도 동일하게 동작한다. if 문에서 기존 비용보다 작을때만 관련 정보를 갱신하므로 이전에 방문했던 노드로 가능 비용을 계산하면 이전 비용보다 커지거나 같아져서 자연스럽게 걸러 진다.
위 함수에서 정보를 받아서 최단 경로를 복원하는 함수를 아래와 같이 만들 수 있다.
- 출발 노드, 도착 노드를 받아서 도착 노드로부터 거꾸로 사전에서 검색해서 경로를 기록한다
- 이때 기록하는 경로는 반대이기 때문에, 출력할때는 출발 → 도착 순이 되도록 한다
def shortest_path (node_from, lead_time, start, end) :
# 경로를 담을 path 문자열 초기화. 끝노드에서 거꾸로 역추적
path = ""
node = end
#출발지까지 올라갈때까지 반복
while node_from[node]:
#지금 노드를 경로에 앞에서부터 이어붙임
path = " -> " + str(node) + path
#현재 노드가 어디서 왔는지 따라감
node = node_from[node]
#마지막 출발 노드를 경로 맨 앞에 붙이고, 전체 경로 문자열 + 최종 비용을 함께 출력
return f"{str(node)+path} (cost = {str(lead_time[end])})"
print(shortest_path(node_from, lead_time, "A", "F"))
>> A에서 F로 가는 최단 경로: A → B → D → F (cost = 6)Bellman-Ford 알고리즘
다익스트라 알고리즘을 사용하게 되면 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하므로 1 → 3 (cost : 10)의 경로를 선택한다. 음수 간선이 존재하면 최단 거리를 찾을 수 없다.
벨만-포드 알고리즘을 사용하면 매번 모든 간선을 전부 확인하므로 1→2→3 (cost: 20-15 = 5)의 경로로 최단 거리를 찾을 수 있다.
동작 방식
- 시작 정점의 거리를 0으로, 나머지는 ∞로 초기화
- 모든 간선에 대해 V-1번 반복하며 다음 작업 수행 :
- V : 정점의 개수
- if distance[u] + weight < distance[v] :
- → distance[v] = distance[u] + weight
- 마지막에 한 번 더 순회해서 갱신이 일어나면 음수 사이클 존재
사용 예시
- 금융/거래 그래프 (이익 / 손실이 음수일 수 있는 경우)
- 루프 감지해야 하는 시스템
- 사이클 검출 및 탐색이 필요한 알고리즘
Floyd-Warshall 알고리즘
모든 정점 간의 최단 거리를 구하는 알고리즘
A → B, A→C, B→C 등 전체 쌍 간 거리 계산하며, 음수 간선을 허용하지만. 음수 사이클 감지는 못함
동작 방식
- 거리 배열 dist[i][j]를 인접 행렬로 초기화
- 세 겹의 반복문 사용 :
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]모든 정점 쌍 (i, j)에 대해서, k를 거쳐 가는 경로가 기존 경로보다 짧다면 갱신한다. 즉, 모든 경로는 다른 노드를 중간에 거쳐가는 경로를 통해 더 최적화 될 수 있다.
03. 플로이드 와샬 알고리즘
# 플로이드 와샬 알고리즘 플로이드 와샬(Floyd Warshall) 알고리즘 역시 앞에서 알아 보았던 최단 경로 알고리즘 중 하나 입니다. 다익스트라 알고리즘은 출발점에서 모…
wikidocs.net
가중 그래프의 최소 스패닝 트리 (MST)
신장 트리(Spanning Tree)란?
n개의 노드를 모두 연결하는 최소한의 방법을 신장 트리라 한다.
n개의 노드를 모두 연결하려면 n-1개의 간선이 필요하고, 신장 트리를 만드는 방법은 $n^{n-2}$ 개가 있다.
이러한 간선을 이용해서 신장 트리를 만들면 사이클을 만들 수 없다.
Kruskal
모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구할때 사용한다. 크리스칼 알고리즘은 그리디 알고리즘과 유니온 파인드 알고리즘을 사용하여 구할 수 있다.
** 유니온 파인드 : 서로소 집합을 빠르게 관리하기 위한 자료구조 (서로소 = 겹치지 않는 집합)
✅ 간단한 동작 흐름
- 처음엔 모든 원소가 자기 자신이 부모 (자기 자신이 집합의 대표)
- union(a, b) → 두 집합을 하나로 합쳐
- find(x) → x의 집합 대표 (root)을 찾음
- find(a) == find(b) → 참 일때, 같은 집합에 속해있음
✅ 크루스칼 동작 흐름
- 모든 간선들을 오름차순으로 정렬한다
- 가중치가 작은 간선부터 선택하여 정점들을 유니온 파인드로 연결한다
- 유니온 파인드로 두 정점이 이미 연결되어 있다면 스킵한다
- 2~3번을 반복하여 모든 간선이 연결되면 최소 신장 트리를 구할 수 있다
***만약 사이클이 생긴다면, 가중치가 큰 연결선을 제외한다
01. 크루스칼 알고리즘
# 크루스칼 알고리즘 크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보겠습니다. 이 알고리즘은 모든 정점을 포함하고, 사이클이 없는 연결 선을 그렸을 때, 가중치…
wikidocs.net
Prim
크루스칼과 동일하게 그리디 알고리즘을 사용하지만, 유니온 파인드가 아닌 우선순위 큐를 사용한다
- 임의의 정점을 선택해 큐에 넣음
- 방문한 적이 없는 정점들 중 가중치가 최소인 정점을 큐에 넣는다
- 모든 정점이 포함될때 까지 1, 2를 반복한다
Kruskal vs Prim
그래프 내 간선이 많은 경우는 프림, 간선이 적은 경우는 크루스칼 알고리즘이 유리하다. 결국, 어떤걸 써도 최소 신장 트리가 1개라면 결과는 같음, 과정이 다를 뿐. (MST가 복수 정답이 있을 수 있지만, 모든 간선의 가중치가 서로 다르면 매 순간 선택이 한 가지 밖에 없기에, 답은 1개이다)
11-04. 가중 그래프에서 최단 경로 찾기
## 다익스트라(Dijkstra) 알고리즘 앞서 공부한 너비 우선 탐색으로 찾은 경로는 중간 노드의 개수가 최소이지만, 최단 경로는 아니다. 다익스트라 알고리즘은 가중 그래프에…
wikidocs.net