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

그래프(Graph)

---

그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.

 

그래프의 종류는 크게 3가지로 나뉜다.

1. 무방향 그래프(undirected graph)
2. 방향 그래프(directed graph)
3. 가중치 그래프(weighted graph)

 

 

더 넘어가기 전에, 그래프에서 알아야할 용어가 있다.

1. 싸이클
2. 분절점

 

 

위의 개념들을 익혔다면 그 다음으로 익혀야할 건 그래프의 탐색이다.

그래프에서 탐색은 가장 기본적인 연산이지만, 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결될만큼 중요하다.

그래프의 탐색 방법은 2가지다. (2가지 밖에 없다 !)

1. 깊이 우선 탐색(DFS : Depth First Search)
2. 너비 우선 탐색(BFS : Breath First Search)

 

DFS/BFS에 대한 설명은 생략

 

 

 

그래프의 응용

---

위의 그래프의 기본 개념을 숙지했다면 그래프가 어디에 응용되는지를 파악해야 한다.

여기서 아주 아주 중요한 2가지가 나온다 !!!! (아마 학부 수준에서 배우는 자료구조의 끝판왕이 아닐까싶다)

1. 최소비용 신장트리
2. 최단 경로

 

일단 2가지만 기억하자 !

최소비용 신장트리를 만들기 위해선 크루스칼 알고리즘이 사용된다. ( 현재 가장 적합한 알고리즘으로 알려져 있음 )

최단경로를 찾기 위해선 다익스트라 알고리즘이 사용된다.