[Graph]

1. 구성 요소

1) node(vertex)

• 그래프를 구성하는 각각의 원소들을 말합니다.

2) edge

• 그래프의 node들간의 연결 관계를 나타낸 것을 말합니다.

3) path

• node A와 node B가 있을때 두 node를 연결하는 edge들의 나열을 말합니다.

4) cycle

• 시작 node와 도착 node가 같은 path를 말합니다.

5) simple path & simple cycle

• 같은 node를 두 번 이상 방문하지 않는 path 혹은 cycle을 말합니다.

6) directed graph

• node들간의 관계를 나타내는 edge에 방향이 있는 그래프를 말합니다.

7) undirected graph

• node들간의 관계를 나타내는 edge에 방향이 없는 그래프를 말합니다.
• bidirection graph라고도 합니다.

8) multiple edge

• 두 node사이의 관계를 나타내는 edge가 두개 이상인 경우를 말합니다.

9) loop

• edge의 양 끝 node가 같은 경우를 말합니다.

10) weight

• edge에 weight가 부여되는 경우를 말합니다.
• weight에 대한 언급이 없는 경우 그냥 1을 넣어주도록 합시다.

11) degree

• node에 연결되어있는 edge의 개수를 의미합니다.
• directed graph의 경우 들어오는 edge와 나가는 edge를 구분하여 in-degree, out-degree로 나누어서 계산합니다.

2. 표현 방법

1) adjancy matrix (인접 행렬)

• node의 개수를 V라고 할때 VxV크기의 이차원 배열을 통해 node간의 edge를 나타내는 그래프 표현 방법입니다.
• 배열의 원소로는 weight를 넣어주고 edge가 없는 경우는 보통 0 혹은 inf를 넣어줍니다.
• 공간복잡도가 O(VxV)입니다.
• 모든 노드들의 연결관계를 조사할 경우 시간복잡도는 O(VxV)입니다.

2) adjancy list (인접 리스트)

• 각 node들 마다 linked list를 이용하여(c++에서는 vector를 이용합시다) 연결되어있는 node들을 표현하는 그래프 표현 방법입니다.
• 만약 weight가 있는 경우 list의 원소로 node 이름과 weight를 쌍으로 넣어주도록 합니다.
  ex) {(3,2), (1,4)} - node3과의 edge에는 weight 2
• 공간복잡도가 O(E)입니다.
• 모든 노드들의 연결관계를 조사할 경우 시간복잡도는 O(E+V)입니다.

3) edge list (간선 리스트)

• 배열을 이용하여 edge들을 순서에 따라 쭉 나열하고 index로 사용할 배열이 또 따로 하나 필요한 방법입니다.
• 정말 필요한 특수한 경우가 아니면 거의 사용 안합니다.

3. 그래프 탐색

그래프에서 탐색이란 임의의 node에서 시작하여 연결되어 있는 모든 node를 1번씩 방문하는 경우를 말합니다.

1) DFS - 깊이 우선 탐색

• stack을 이용하여 가능한 탐색이 불가능할때까지 탐색을 한 후 stack에 저장하고 꺼내서 사용하는 방법으로 구현하며 보통은 c++에서는 함수가 stack의 형식으로 구현이 되기 때문에 재귀함수를 이용하여 많이 구현합니다.

2) BFS - 너비 우선 탐색

• queue를 이용하여 현재 node와 연결되어있는 바로 다음 node들을 우선 탐색하여 queue에 저장한 후 탐색할 node가 없으면 queue에서 꺼내서 다시 탐색하는 방법으로 구현하며 queue에 저장된 원소가 없을 때 까지 탐색을 진행하면 됩니다.