-
1. Graph란?
그래프란 노드와 그 노드를 연결하는 간선으로 이루어진 자료구조를 의마한다
* 그래프에서 사용되는 용어들
1. 정점(=vertex) : 노드와 같은 뜻을 가지고 있다.
2. 간선(=edge) : 정점 또는 노드를 이어주는 선을 의미한다.
3. 정점의 차수(degree) : 하나의 정점에 인접한 정점의 수2. Grpah의 종류
1. 무방향 그래프
정점을 이어주는 간선을 통해 "양방향"으로 이동이 가능하다.2. 방향 그래프
정점을 이어주는 간선을 통해 "단방향"으로 이동이 가능하다.3.Grpah의 표현방식
1 인접 행렬
인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다.
- 장점
1. 구현이 쉽다
2. 연결 여부를 쉽게 파악 할 수 있다.
( 행렬 내부에서 0 | 1 인지만 파악하면 되기 때문에, O(1)의 속도로 빠르게 찾을 수 있다 )
- 단점
1. 정점과 연결된 부분을 찾는 시간이 많이 소요된다.
( I라는 정점에 연결된 요소를 찾기 위해서는 adj[i][1] ~ adj[i][N] 를 모두 확인 해야 한다 )
2. 인접 리스트
각각의 노드에 연결된 노드들을 원소로 갖는 리스트들의 배열을 의미.
-장점
- 연결된 간선만을 저장하기에, 적은 메모리를 차지한다.- 연결된 모든 정점을 찾기에 용이하다.
-단점
- I-J 간 연결 여부를 확인 하기 위해서는 adj[i]를 모두 확인 해야함으로, O(V) 만큼의 시간이 소요된다.
'CS > Algorithm Theory' 카테고리의 다른 글
[ Algo Theory ] 버블 / 삽입 / 선택 정렬 (0) 2021.05.22 [알고_이론] 퀵정렬 (Quick sort _ by python ) (0) 2021.01.27 [알고_이론] 선택정렬 (Selection sort _ by python ) (0) 2021.01.27 [알고_이론] 삽입정렬 (insertion sort _ by python ) (0) 2021.01.27 [알고_이론 ] 버블정렬 ( bubble sort by python ) (0) 2021.01.27 댓글