Data structures - Graphs
Introduction
graph
그래프는 Vertices(Node)와 edge(arcs, lines)로 구성된 비선형 자료구조이다.
그래프 그림을 그리는 방식과 구현 방식이 다르다는 게 흥미롭고 낯선 부분이었다.
graph = [(C, A, 4), (A, C, 1), (B, C, 6),
(A, B, 4), (C, B, 1), (C, D, 2)]G = (V, E)
undirected graph / digraph
그래프에는 두 종류가 있는데, 하나는 방향성이 존재하지 않는 Undirected graph이다. 다른 하나는 방향이 있는 Directed graph(digraph)이다. Undirected graph는 (u, v)와 같이 표기하며, 방향이 없으므로 (u, v)나 (v, u)나 같은 의미이다. Digraph(Directed graph)는 각 edge가 방향을 가지고 있다. <u, v>와 같이 표기한다.
# example of undireted graph
G = (V, E)
V = [0,1,2,3] # vertices
E = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)] # edges방향이 없는 undirected graph의 예시다. E 리스트는 6개의 튜플로 이루어져 있다. 각 튜플은 하나의 edge를 의미하며, 튜플의 0번째 원소와 1번째 원소를 연결한다는 뜻이다.
applications
Graph는 구성요소 간의 관계를 매우 간단하게 표현할 수 있는 자료구조라서 널리 사용된다.
Graph의 구성 요소인 Vertex와 Edge를 다른 것으로 대치시키기만 하면 된다 :)
예를 들면, Communication Network를 표현하는 경우에는
Vertex를 하나의 도시로, Edge를 도시 간의 커뮤니케이션 연결망이라고 정의할 수 있다.
그래프는 교통망을 표현하기에도 매우 효과적인 도구인데, 그래프의 weight나 digraph를 사용하면 다양한 것을 표현할 수 있다. 예를 들면, vertex를 city로 두고, edge에 연결하는 city을 이동하는 데 걸리는 시간/거리를 weight로 할당해두면, Driving cost를 계산하는 데 그래프를 쓸 수도 있다.
교통망을 digraph를 이용해서 표현하면, 이동거리 간의 방향성(어느 곳은 일방통행)도 나타낼 수 있다.
complete undirected graph
Complete undirected graph란, 모든 노드가 모든 노드와 '한번씩' 연결되어있는 그래프를 의미한다.
number of edges
- undirected graph
vertex의 개수를 가지고, 거꾸로 edges의 개수를 구해볼 수 있다.
물론, edges를 어떻게 그리느냐에 따라서 graph의 엣지의 개수는 달라질 것이지만, 만약에 그래프가 complete undirected graph라면 직접 계산해줄 수 있다.
complete undirected graph는 한 vertex가 다른 모든 vertex에게 연결되어야 한다. 이 경우의 수는 n(n-1)과 같다.
그러나 undirected graph에서 (u,v) == (v, u)이므로, 1/2배 해주어야 한다.
따라서 complete undirected graph의 edges의 개수는 n(n-1)/2이며, 그냥 undirected graph의 edges의 개수는 n(n-1)/2개보다 같거나 작다.
- digraph
계산해주는 방식은 동일하다. Digraph의 경우, <u,v> != <v,u>이므로, 1/2배 해줄 필요가 없다. 따라서 complete directed graph의 edges의 개수는 n(n-1)개이며, 그냥 digraph의 edges의 개수는 n(n-1)개보다 같거나 작다.
vertex degree
vertex degree는 하나의 vertex에 연결된 edge의 수를 말한다.
위 그림을 예로 들어서 설명하자면,
1이라는 vertex에 연결된 edge의 수는 1개이므로 degree(1) = 1
0의 경우 연결된 edge가 없어서 degree(0) = 0과 같다.
sum of vertex degrees
sum of degrees = 2e (e는 edge의 개수)
vertex degree of digraph
in-degree / out-degree
vertex를 기준으로 나에게 향해오는 것은 in-degree, 나가는 것은 out-degree로 계산해주면 된다.
in-degree(2) = 1
out-degree(2) = 1
in-degree(8) = 0
out-degree(8) = 2
sum of in- and out-degrees
중복으로 세지 않기 때문에, in degree와 out degree의 합은 모두 e로 동일하다.
graph problems
path finding
path finding 문제는 말 그대로 a에서 b로 가는 경로를 찾는 문제다.
여러 가지 경우를 찾아 가장 최적의 값으로 계산해줄 수도 있다.
connectedness problem
<connected graph>
모든 vertices의 쌍에 일정한 path가 존재하는 undirected graph를 connected path라고 한다.
만약에 connect 되지 않은 부분이 존재한다면, 그 일부분을 connected components라고 한다.
<connected component>
connected component는 vertices끼리 모두 연결된 최대의 subgraph를 의미한다.
(최대의 연결된 subgraph여야 함. 만약에 vertices와 edges를 더 더해도 connected 상태를 유지한다면, 그건 connected component가 아닌 것임)
<communication network problems>
communication network problems란, components를 찾아서 모든 vertices가 연결되어있는지 검증하는 문제를 말한다.
가장 가볍고 잘 작동하는 link를 찾는 것이 목표
이때 cycle이라는 용어가 등장하는데, cycle이란, 이미 연결된 vertices를 또 연결해서 중첩된 부분을 말한다.
<tree>
tree는 일종의 그래프이다.
그래프는 vertices와 edge로 구성된다는 것만 규정하므로 tree에 어떤 속성이 더 추가되어있다.
tree는 graph이지만, 그 중에서도 모든 원소가 [connected]되어있고, [acyclic]한 그래프이다.
그래서 트리는 n개의 vertex를 n-1개의 edge로 딱 효율적으로 연결한다.
minimum cost spanning tree problem
<spanning tree>
spanning tree는 특정한 조건을 만족하는 그래프의 부분집합을 말한다.
이때 조건은 다음과 같다.
[1] 원래 그래프의 모든 vertices를 포함해야 한다.
[2] 그리고 트리여야 한다.
- 모든 원소가 [connected]되어있고, [acyclic]한 그래프
- n개의 vertices를 가지고, n-1개의 edge를 가진다.
<minimum cost spanning tree problem>
minimum cost spanning tree 문제란, 말 그대로 그래프를 가장 효율적으로 만드는 트리를 찾는 것이다.
graph representation
adjacency matrix/list
그래프는 matrix나 list를 이용해서 구현할 수 있다.
<adjacency matrix>
adjacency matrix를 채우는 방법은 매우 간단하다.
일단 n개의 vertices가 있다면, n*n 행렬을 만들고, 모든 값을 0으로 초기화한다.
그리고 행렬 내부 요소들의 값을 정해주는 규칙에 따라 값을 정한다.
i vertices와 j vertices를 연결하는 (i, j)라는 edge 가 존재하는 경우에만, A(i, j) = 1로 수정해준다.
이는 그래프가 digraph일 때, undirected graph일 때 모두 적용될 수 있다.
그렇지만, undirected graph일 경우에는, A(i, j)나 A(j, i)나 동일한 의미를 갖기 때문에 symmetric 대칭 행렬이 된다.
이 경우에는, 대칭 아래 행렬을 버려 메모리 낭비를 막을 수 있다 :)
"Inverse adjacency matrix/list"
graph는 undirected가 디폴트 상태라 그런가, digraph의 adjacency matrix는 특별히 'inverse'라고 해둔다.
=> 성능
공간 복잡도 : n*n 행렬이니까, n**2 space가 필요하다. undirected graph의 경우 (n-1)n/2 space
시간 복잡도 : O(n)
<adjacency list>
adjacency list는 가까운 vertices를 연결한 linear list를 의미한다.
list가 늘 그렇듯이.. array 버전과 linked list 버전이 있다.
aList는 linked list로 adjacency list를 구현한 것이다.
aList[1]은 1과 연결된 2, 4를 chain node로 연결해두었다.
chain node의 총합 역시 undirected와 digraph가 다른데
undirected graph의 경우, 2e
digraph의 경우 e개가 필요하다.
<weighted graphs>
비용을 계산하고, 비용을 절감하는 방향으로 path를 계산할 때 유용하다.
adjacency matrix/list에서 구현하는 방식은 매우 간단한데,
adjacency matrix의 경우, A(i, j)의 값을 1이 아니라, cost(i, j)로 수정해주면 된다.
adjacency list의 경우, chain node의 값을 (vertex, cost)로 수정해주면 해결된다.
graph search methods
이번에는 드디어 그래프 탐색이다 :)
그래프를 탐색하는 방식에는 DFS depth first search와 BFS breadth first search 방식이 있다.
이를 파이썬으로 구현해볼 것이고, 스켈레톤 코드는 다음과 같다.
class graph:
def __init__(self, g):
self.graph = g
def dfs(self):
pass
def bfs(self):
pass
# undirected graph
gr = [(1,2), (1,4), (2,5), (2,3), (3,5), (6,9), (8,9), (10,11), (7,7)]
g = graph(gr)
g.dfs()
g.bfs()
DFS depth first search
Sudo code
def dfs(self, vertex):
# 현재 작업 중인 vertex를 작업한 것으로 표시한다
# for temp vertex와 연결된 다른 vertex에 대하여
# 각각 모두 탐색한다
구현 완료~!
<1> linear
list 버전
class graph:
def __init__(self, g):
self.graph = g
self.label = []
def dfs(self, vertex):
print(vertex)
self.label.append(vertex)
for i, j in self.graph:
if i == vertex:
if j not in self.label:
self.dfs(j)
if j == vertex:
if i not in self.label:
self.dfs(i)
def bfs(self):
pass
# undirected graph
gr = [(1,2), (1,4), (2,5), (2,3), (3,5), (6,9), (8,9), (10,11), (7,7)]
gr = [(1,2),(1,4), (2,5), (4,5), (3,5)]
g = graph(gr)
g.dfs(1)
g.bfs()<2> linked list 버전
class Node:
def __init__(self, value):
self.data = value
class Graph:
def __init__(self):
self.graph = {}
self.visit = []
def create(self, v, data):
node = Node(data)
if v not in self.graph:
self.graph[v] = []
self.graph[v].append(node)
def dfs(self, v):
self.visit.append(v)
for node in self.graph[v]:
if node.data not in self.visit:
self.dfs(node.data)
g = Graph()
for v, node in [(1,2), (1,3), (2,1), (2,4), (2,5), (2,7), (3,1), (3,4), \
(3,5), (4,2), (4,3), (4,7), (5,2), (5,3), (5,6), (5,8), \
(6,5), (6,7), (6,8), (7,2), (7,4), (7,6), (8,5), (8,6)]:
g.create(v, node)
g.dfs(1)
print("dfs ", g.visit)
DFS의 특징은 start vertex에서 연결된 모든 vertices에 방문한다는 것이다.
<application 1 - path>
DFS를 이용해서 v에서 u로 가는 path를 찾아낼 수 있다.
알고리즘은 DFS를 활용하되, tmp vertex == u가 되면 return해주면 된다.
이 알고리즘의 시간 복잡도는 O(n^2) (matrix version), O(n+e)(list version)이다.
<application 2 - connectedness>
그래프가 connected graph인지 확인하는 건 매우 간단하다.
일단 DFS를 돌리고, visited list의 길이가 graph의 vertices 개수와 같은지 체크하면 된다.
=> 시간 복잡도는 matrix 버전에서 O(n^2), list 버전에서 O(n+e)다.
<spanning tree>
다시 spanning tree의 정의를 보면, 그래프의 모든 노드를 지나면서도 효율적으로 연결된 트리를 말한다.
BFS 탐색 기법을 이용해서 spanning tree를 탐색할 수 있다 .
일단 dfs를 임의의 한 vertex에서 시작한 뒤에, n-1개의 edges로 모든 vertices를 방문한다면, 이것이 spaning tree(DF spanning tree)가 된다.
이를 탐색하기 위한 시간은
depth first search와 같이, adjacency matrix를 쓰면 O(n^2), list를 쓰면 O(n+e)가 걸린다.
BFS Breadth-first search
<BFS는?>
일단 vertex에서 시작해서 FIFO queue를 이용한다.
queue가 빌 때까지,
- queue에서 vertex를 제거하고(dequeue)
- 제거한 vertex에 인접한 모든 vertices에 방문하여서
- 그 vertices들을 모두 queue에 enqueue해준다.
level order 트리 탐색과도 유사한 성격을 갖는다.
<구현>
def bfs(self, vertex):
self.visit.append(vertex)
self.l.append(vertex)
while len(self.visit) > 0:
tmp = self.visit.pop(0)
print(tmp)
for i, j in self.graph:
if i == tmp and j not in self.l:
self.visit.append(j)
self.l.append(j)
if j == tmp and i not in self.l:
self.visit.append(i)
self.l.append(i)
time complexity
O(n+3) => list version
minimum cost spanning tree
weighted connected graph에 대해서
가장 최적의 경로를 가진 spanning tree를 찾는 문제
edge selection strategies
> edge rejection strategies
connected graph로 시작해서,
확장해나가다가 cycle이 발생하면, 가장 높은 cost를 갖는 edge를 제거한다.
cycle이 남아있지 않으면 정지한다.
> edge selection strategies
반대로 edge를 하나씩 선택해가는 strategies는 세 가지 방식이 있다.
첫째는 kruskal의 방법,
둘째는 prim의 방법,
마지막은 sollin의 방법이다.
<kruskal's method>
step 0. n개의 vertex를 가져온다. edge는 0개다.
step 1. edges를 cost의 오름차순으로 정렬한다.
step 2. cost가 작은 순서대로, cycle을 만들어내지 않는 edge라면 추가해준다.
<prim's method>
step 0. 1 vertex tree로 시작한다.
step 1. vertex에 인접한 X 가장 저렴한 vertex/edge를 더해나간다.
step 2. n-1 개의 edges가 있을 때 종료한다.
<sollin's method>
step 0. n vertex forest로 시작한다.
step 1. 각 vertex는 인접한 vertex 중에 가장 작은 cost를 가진 vertex와 연결한다.
step 2. cycle이 존재하는 건 제거한다.
step 3. 1개만 남아있을 때까지 반복한다.
> cycle check - find, union
different set이면, union해주고 / same set이면, cycle 발생하므로 pass해준다