그래프
수학에서, 좀 더 구체적으로 그래프 이론에서 그래프란 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조를 말한다
'쾨니히스베르크의 다리 문제' 란 지금으로부터 300여 년 전 프로이센 공국의 쾨니히스베르크에는 프레겔 강이 흐르고 있었다. 프레겔 강에는 2개의 큰 섬이 있었고, 섬과 도시를 연결하는 7개의 다리가 놓여 있었다. 어느날 도시의 시민 한명이 ''이 7개의 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?" 라는 흥미로운 문제를 내면서 시작되었다.
오일러 경로
오일러는 모든 정점이 짝수 개의 차수를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다.
아울러 모든 간선을 한 번씩 방문하는 유한 그래프를 일컬어 오일러 경로라고 부르며, 우리가 잘 아는 한붓 그리기라고도 말한다.
해밀턴 경로
각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로를 말한다.
간선을 기준으로 하는 오일러와 달리 해밀턴 경로는 정점을 기준으로 한다.
•
해밀턴 경로 : 한 번만 방문하는 경로
•
해밀턴 순환 : 한 번만 방문하여 출발지로 돌아오는 경로
•
외판원 문제 : 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로
그래프 순회
그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말한다
DFS (깊이 우선 탐색)
주로 스택이나 재귀로 구현, 재귀를 이용하면 좀 더 간단하게 구현할 수 있음
백트래킹을 통해 뛰어난 효용을 보임
graph = {
1: [2, 3, 4],
2: [5],
3: [5],
4: [],
5: [6, 7],
6: [],
7: [3]
}
Python
복사
재귀 구조로 구현
수도코드
DFS(G, V)
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
Plain Text
복사
python
def recursive_dfs(v, discovered=[])
discovered.append(v)
for w in graph[v]:
if not w in discovered:
discovered = recursive_dfs(w, discovered)
return discovered
Python
복사
스택을 이용한 반복 구조로 구현
수도코드
DFS-iterative(G, v)
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Plain Text
복사
python
def iterative_dfs(start_v):
discovered = []
stack = [start_v]
while stack:
v = stack.pop()
if v not in discovered:
discovered.append(v)
for w in graph[v]:
stack.append(w)
return discovered
Python
복사
BFS 너비 우선 탐색
주로 큐로 구현
그래프의 최단 경로를 구하는 다익스트라 알고리즘 등에 유용하게 쓰임
큐를 이용한 반복구조로 구현
수도코도
BFS(G, start_v)
let Q be a queue
label start_v as discovered
Q.enqueue(start_v)
while Q is not empty do
v := Q.dequeue()
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do
if w is not labeled as discovered then
label w as discovered
w.parent := v
Q.enqueue(w)
Plain Text
복사
python
def iterative_bfs(start_v):
discovered = [start_v]
queue = [start_v]
while queue:
v = queue.pop(0)
for w in graph[v]:
if w not in discovered:
queue.append(w)
discovered.append(w)
Python
복사
시작 시 discovered에 그래프의 시작 정점을 넣고 시작한다.
백트래킹
백트래킹이란 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용
백트래킹은 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는 데서 유래했다.
DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS는 백트래킹의 골격을 이루는 알고리즘
주로 재귀로 구현
운이 좋으면 시행착오를 덜 거치고 목적지에 도착할 수 있지만 최악의 경우에는 모든 경우를 다 거친 다음에 도착할 수 있어 브루트 포스와 유사하지만 한 번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기하기 때문에 브루트 포스보다는 더 효율적인 방식
제약 충족 문제
제약 충족 문제란 수많은 제약 조건을 충족하는 상태를 찾아내는 수학문제를 일컫는다.
백트래킹은 제약 충족 문제를 풀이하는 데 필수적인 알고리즘