TIL_Graph

jhin·2020년 6월 1일
0

IM19

목록 보기
17/21

그래프의 개념

그래프는 정보를 담는 노드(Node)와 그 노드를 연결하는 간선(Edge)로 이루어진 자료 구조이다. 일반적으로 사용되는 자료구조이며연결되어 있는 객체간의 관계를 표현할 수 있는 자료 구조이다(ex 전기 회로의 소자, 지하철 노선의 최단 경로, 지도 상의 도시들 간의 관계).

위의 구조가 대표적인 그래프의 예시라고 할 수 있다.

그래프의 표현

1. 인접 리스트

그래프를 표현하는 가장 일반적인 방식은 인접 리스트(Adjacency List)이다.
모든 노드(혹은 정점)에 인접한 노드들을 리스트로 표시한 것이다.

1. 먼저 해당 그래프의 노드들을 배열의 인덱스에 각각 집어넣는다.
2. 이후 해당 인덱스의 노드와 인접한 노드들을 나열해서 저장한다.

이때 모든 노드들의 개수는 간선의 수 2 가 된다. 노드의 수(2m) = 간선의 수(m) 2이다.
위 예시의 경우, 간선의 수는 4개이고 따라서 노드의 수는 8이다.

출처
https://www.youtube.com/watch?v=fVcKN42YXXI
https://blog.naver.com/kbs4674/220727852469
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

profile
Maktub.

0개의 댓글