[자료구조] 그래프(Graph)

1. 그래프

vertex와 edge로 구성된 한정된 자료구조. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다

2. 그래프 종류

1. 무방향 그래프
두 정점을 연결하는 간선에 방향이 없는 그래프.
2. 방향 그래프
두 정점을 연결하는 간선에 방향이 있는 그래프.
3. 완전 그래프
한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프.
4. 부분 그래프
기존 그래프에서 일부 정점이나 간선을 제외한 그래프.
5. 가중 그래프
정점을 연결하는 간선에 가중치(weight)를 할당한 그래프.
6. 유향 비순환 그래프
방향 그래프에서 사이클이 없는 그래프.
7. 연결 그래프
떨어져 있는 정점이 없는 그래프.
8. 단절 그래프
연결되지 않는 정점이 있는 그래프.

3. 용어

그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때, 두 정점을 인접한다 하고 간선 (Vi, Vj)는 정점 Vi, Vj에 부속한다.

• 차수(Degree)
정점에 부속되어 있는 간선의 수
• 경로(Path)
정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
• 사이클(Cycle)
단순 경로 중,

4. 탐색

1. 깊이 우선 탐색(DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

2. 너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

출처
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html