자료구조 - Graph 학습

Graph 정의

그래프 G는 두 집합 V, E로 나타낸다.

1. V(G) : 노드(node) 혹은 정점(vertex)의 집합
2. E(G) : 정점을 잇는 엣지(edge)의 집합

Graph의 특징

1. 자기 간선(self-edge)를 가질 수 없다.
   –> (v, v) or <v, v>를 가질 수 없다.
2. 두 정점 사이에 같은 Edge를 여러 개 가질 수 없다.

Graph traversal(그래프 순회)

그래프 G에서 한 정점 v가 주어졌을 때, 모든 정점을 중복되지 않게 방문하는 것

1. 너비 우선 탐색(BFS, breadth first search)

2. 깊이 우선 탐색(DFS, depth first search)