그래프 개념
노드와 그 노드를 연결하는 간선으로 이루어진 자료 구조다
중요한 용어
정점(vertiex): 노드라고도 하며, 데이터가 저장되는 공간
간선(edge): 노드간의 관계를 나타내고, 노드를 연결하는 선
차수(degree): 하나의 정점에 인접한 정점의 수
레벨(Level): 트리의 높이 혹은 깊이
구현 방법
그래프를 구현하는 방법에는 2가지가 있다 인접행렬과 인접리스트방식이다
인접행렬(Adjacency MAtrix)
그래프의 노드를 2차원 배열로 만든 것이다 배열의 각 요소에는 간선의 유무를 체크하는 0 또는 1을 넣는다
그래프에 간선이 많은 경우 주로 사용된다
장점: 모든 정점의 정보를 담기 때문에 정보를 조회할 때 O(1)의 시간복잡도면 가능하다. +구현이 쉽다
단점: 모든 정점의 정보를 대입해야 하므로 O(n^2)의 시간복잡도가 소용된다 +저장공간이 많이 소요됨
인접리스트(Adjacency List)
그래프의 노드를 리스트로 만든 것이다 각각의 정점에 인접한 정점들을 리스트로 표시한다
그래프 내에 간선이 적은 경우 주로 사용된다
장점: 특정 노드에 인접한 노드들과 모든 간선의 수를 쉽게 구할 수 있다
단점: 간선의 존재 여부와 정점의 차수를 구할 때 차수가 많을 때 시간이 많이 소요된다 +구현이 어렵다
그래프 종류
무방향 그래프 : 간선이 양방통행이다
방향 그래프 : 간선이 일방통행이다
가중치 그래프 : 간선에 비용이나 가중치가 있다
완전 그래프 : 모든 정점이 서로 연결되어 있다
그래프 탐색
그래프의 탐색에는 대표적으로 깊이 우선 탐색(DPS)과 너비 우선 탐색(BFS)이 있다.