[Graph] 그래프의 종류와 관련 알고리즘 한꺼번에 훑어보기

TL;DR

그래프는
<노드 Node>와 <엣지 Edge>로 구성된 데이터 구조임.

즉,
'노드 사이의 관계'를 표현해놓은 데이터 구조이기 때문에
이 관계와 관련된 문제를 해결하는 것이 관건임.

프로그래밍 세계에는
노드 간 관계의 경향에 따라
몇 가지 일반화되어 있는 그래프의 종류가 있으며,

각 종류에 따라
주로 등장하는 문제와
이를 해결하기 위해 주로 활용하는 알고리즘이 존재함.

----------------------------------------------
<비전공자 문과생에게 추천하는 학습법>

경험상,
그래프 종류와 알고리즘을
추상적으로 이해하는 데 시간을 투자하기보다는

실제로 각 종류의 그래프를
어떻게 코드로 표현하는지,
어떤 실제적인 문제가 주어지며,
어떤 절차로 알고리즘이 구현되는지

여러가지 구체적인 사례를 먼저 보고
이론으로 다시 돌아가서 학습하는 것이
효율이 훨씬 좋았음.

---

1. 그래프 Graph

1) 정의

: 노드 Node(혹은 Vertex)와 엣지 Edge(혹은 Arc)로 구성된 데이터 구조(edge는 무방향성 일때, arc는 방향성이 있을 때)
: 추상 데이터 타입 Abstract Data Type임.

2) 구현 수단 (Concrete Data Structure)

: 노드 & 엣지로 노드 사이의 관계를 표현하는 것이 곧 그래프의 구현
: 방향성 유무, 가중치 유무에 따라 리스트 내부 요소에 정보를 추가하여 표현
: 각 노드를 나타내는 key가 0부터 시작하는 int형이 아니라 str형이라면, 각 인덱스에 대응되는 key 값을 mapping할 dictionary를 선언하여 사용.

 - 인접리스트 Adjacency List
  : 전체 수준 리스트의 index = 각 노드의 Key에 대응
  : 각 index에 들어가는 값 = 해당 index 노드에 인접한 노드들을 나열한 리스트
  ex. [ [1], [0, 2], [1, 3], [2] ]

 - 인접행렬 Adjacency Matrix
  : 2차원 배열을 만들어 행과 열 index를 각 노드 key에 대응
  : 각 좌표에 추가한 값으로 인접 여부, 가중치 등을 표현
  ex. [ [0, 0, 1, 0],
           [0, 0, 0, 1],
           [1, 0, 0, 1],
           [0, 1, 1, 0] ]

 - 엣지리스트 Edge List
  : 각 Edge의 시작점과 끝점 정보를 튜플에 담아 표현
  ex. [ (0, 1), (0, 2), (1, 2), (2, 3) ]

---

2. 그래프의 종류

- 노드 간 특수성에 따라 일반화 되어있는 몇 가지 종류

1) 무가중, 무방향성 그래프
  - 각 지점들이 그냥 단순 연결만 되어있는 그래프
  - 쌍방 통행 가능

2) 유가중, 무방향성 그래프
  - 각 지점들을 이동할 때 소요되는 비용/거리/시간 등의 정보가 가중치로 표현된 그래프

3) 유방향성, 무사이클 그래프
  - 모든 지점이 쌍방향으로 이동할 수 없고, 이동 가능한 특정 방향이 있는 그래프
  - 즉, 반드시 어떤 지점이 먼저 방문되어야 비로소 방문할 수 있는 지점들이 존재
  - 즉, 지점 간 순서상의 의존적 관계를 띠는 그래프

4) 연결, 무사이클 그래프 중 최소 신장 트리 Minimum Spanning Tree
  - 모든 지점이 다 연결되어 있지만, 사이클은 없는 트리
  - 기존에 간선이 아주 많은 그래프를 "지점 사이의 비용을 최소화"하는 방향으로 재구성한 결과물
  - 크루스컬, 프림 등의 알고리즘을 활용하여 재구성

5) 이진 탐색 트리 Binary Search Tree
  - 자식노드가 최대 2개이고, 노드의 좌우 위치가 대소관계로 정렬된 형태인 트리
  - 탐색 속도가 무척 빠름

6) B-tree
  - 이진 탐색 트리의 탐색 속도 장점을 살리되, 그 노드의 수를 2개 이상으로 늘려 사용하기 위해 고안된 그래프 형태
  - 한 노드에 키, 데이터, 자식 노드에 대한 포인터 정보를 가짐
  - 데이터 탐색은 매우 빠르지만,
  - 삽입, 삭제 시에는 정렬이 함께 진행되어서 느림

7) Trie
  - 단어 검색에 특화되어있는 트리 구조
  - 단어를 구성하는 글자 하나 하나가 위에서부터 순서대로 자식 노드로 연결되어 있음
  - 연관검색어 등의 서비스를 제공하는 등의 상황에 쓰이는 특수한 데이터 구조 

---

3. 그래프 종류별 연관 알고리즘

- 종류별로 해결해야 할 문제에 따라, 달라지는 주 활용 알고리즘

1) 무가중치, 무방향성 그래프
  - A지점에서 B지점으로 가는 물리적 최단 경로를 구하기 : 너비우선탐색 BFS
  - A지점에서 갈 수 있는 모든 경로를 구하기 : 깊이우선탐색 DFS

2) 유가중치, 무방향성 그래프
  - A지점에서 B지점으로 가는 최소 비용의 경로를 구하기 : 다익스트라 Dijkstra's Algorithm
  - N → N, 모든 정점에서 모든 정점으로 가는 최소 비용 구하기: 플로이드 워셜 Floyd-Warshall Algorithm

3) 유방향성, 무사이클 그래프
  - 어떤 순서로 정렬하여야 모든 노드가 방향을 보존한 상태로 이어질 수 있는지 찾기: 위상정렬 Topological Algorithm

4) 최소신장트리 Minimum Spanning Tree
  - 간선이 아주 많은 그래프를, 최소 비용으로 연결된 사이클 없는 트리 형태로 재구성하기 : 크루스컬 Kruskal, 프림 Prim Algorithm