[자료구조] 그래프(Graph)
그래프(Graph)
그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.
그래프의 종류는 크게 3가지로 나뉜다.
- 무방향 그래프(undirected graph)
- 방향 그래프(directed graph)
- 가중치 그래프(weighted graph)
더 넘어가기 전에, 그래프에서 알아야할 용어가 있다.
- 싸이클
- 분절점
위의 개념들을 익혔다면 그 다음으로 익혀야할 건 그래프의 탐색이다.
그래프에서 탐색은 가장 기본적인 연산이지만, 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결될만큼 중요하다.
그래프의 탐색 방법은 2가지다. (2가지 밖에 없다 !)
- 깊이 우선 탐색(DFS : Depth First Search)
- 너비 우선 탐색(BFS : Breath First Search)
DFS/BFS에 대한 설명은 생략
그래프의 응용
위의 그래프의 기본 개념을 숙지했다면 그래프가 어디에 응용되는지를 파악해야 한다.
여기서 아주 아주 중요한 2가지가 나온다 !!!! (아마 학부 수준에서 배우는 자료구조의 끝판왕이 아닐까싶다)
- 최소비용 신장트리
- 최단 경로
일단 2가지만 기억하자 !
최소비용 신장트리를 만들기 위해선 크루스칼 알고리즘이 사용된다. ( 현재 가장 적합한 알고리즘으로 알려져 있음 )
최단경로를 찾기 위해선 다익스트라 알고리즘이 사용된다.
'Algorithm > Theory' 카테고리의 다른 글
[자료구조] B-트리 (0) | 2020.02.13 |
---|---|
[알고리즘] 최소비용 신장트리(MST) - Kruskal 알고리즘 (0) | 2019.12.12 |
[자료구조] 서로소 집합(Disjoint-Set) (0) | 2019.11.13 |
[알고리즘] 동적 계획법(Dynamic Programming) (0) | 2019.10.24 |
[자료구조] 이분 그래프 (Bipartite Graph) (0) | 2019.09.24 |
댓글
이 글 공유하기
다른 글
-
[자료구조] B-트리
[자료구조] B-트리
2020.02.13 -
[알고리즘] 최소비용 신장트리(MST) - Kruskal 알고리즘
[알고리즘] 최소비용 신장트리(MST) - Kruskal 알고리즘
2019.12.12 -
[자료구조] 서로소 집합(Disjoint-Set)
[자료구조] 서로소 집합(Disjoint-Set)
2019.11.13 -
[알고리즘] 동적 계획법(Dynamic Programming)
[알고리즘] 동적 계획법(Dynamic Programming)
2019.10.24