Graph
Graph
그래프(Graph)는 정점(vertex)의 집합과 간선(edge)의 집합으로 이루어진 자료구조이다.
Graph = (V, E)
- V = sets of vertices
- E = sets of edges
Graph Traversals
그래프 순회에는 대표적으로 DFS와 BFS가 있다.
DFS
Depth First Search의 약자로 깊이 우선 탐색을 한다. 재귀함수 방식이나 스택(stack) 방식으로 구현할 수 있다.
BFS
Breadth First Search로 너비 우선 탐색을 한다. 큐(queue) 방식으로 구현할 수 있다.
Topological Sort
cycle이 없는 directed 그래프 G에서 정점 x가 정점 y를 가리킬 때 정점 y가 정점 x보다 앞서는 것을 topological order라고 하고 topological order로 정렬하는 알고리즘을 topological sort라고 한다.
Spanning Tree
n개의 정점을 갖는 connected, undirected 그래프 G가 존재할 때, spanning tree는 그래프 G의 n개의 정점을 모두 연결하는 n-1개의 간선을 갖는 트리(tree)를 말한다. Spanning tree는 그래프 G의 부분 집합이다. 트리이기 때문에 cycle이 없고 정점이 m개일 때 간선이 m-1개임을 만족한다.
Minimum Spanning Tree
Minimum spanning tree는 connected, undirected, weighted 그래프 G의 spanning tree 중에서 가장 작은 weight cost를 갖는 spanning tree를 말한다. Minimum spanning tree를 구하는 알고리즘으로는 prim 알고리즘과 kruskal 알고리즘 등이 있다.
Shortest Paths
Shortest Paths는 weighted, directed 그래프 G에서 모든 정점을 방문하는 path 중에 가장 weight cost가 작은 path를 말한다. 참고로 undirected 그래프를 쌍방으로 향하는 directed 그래프로 표현한다면 shortest paths에 만족한다. Shortest Paths를 구하는 알고리즘으로는 dijkstra 알고리즘이 있다.
Reference
- https://soar.snu.ac.kr/course/ds/20181/ : Chapter 15. Graph