그래프란
정점과 간선으로 이루어진 자료구조
그래프 용어
정점(vertex) : 노드(node)라고도 하며 데이터가 저장 됨
간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 의미
인접 정점(adjacent vertex) : 간선에 의해 연결된 정점
단순 경로(simple-path): 같은 간선을 자나가지 않는 경로
차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수
진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수
그래프 구현 방법
-인접 행렬
-인접 리스트
인접 행렬
그래프의 노드를 2차원 배열로 만든 형식
인접 정점인 경우 1, 아닌 경우 0으로 표시
시간복잡도
두점에 대한 연결 정보 조회 : O(1)
인접행렬 그래프를 만드는 경우 : O(n²)
인접 행렬 특징
- 구현이 비교적 간편
- 2차원 배열이 필요하기에 필요 이상의 공간이 낭비
인접 리스트
그래프의 노드들을 리스트로 표현한 형태
시간 복잡도
정점들의 연결 정보 탐색 : O(n) (n : 간선의 개수)
인접 리스트 특징
- 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적음
- 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸림 (배열보다 검색 속도 느림)
- 구현이 비교적 어려움
그래프 종류
무방향그래프
두 정점을 연결하는 간선에 방향이 없는 그래프
방향그래프
두 정점을 연결하는 간선에 방향이 존재하는 그래프
간선의 방향으로만 이동 가능
가중치그래프
두 정점을 이동할때 비용이 드는 그래프
완전그래프
모든 정점이 간선으로 연결되어 있는 그래프
'자료구조' 카테고리의 다른 글
| 플로이드 와샬(Floyd Warshall) 알고리즘 (0) | 2021.05.07 |
|---|---|
| 다익스트라 알고리즘 (Dijkstra Algorithm) (0) | 2021.05.07 |
| 덱 (Deque) (0) | 2021.05.07 |
| 우선순위 큐 (Prioity Queue) (0) | 2021.05.06 |
| 큐 (Queue), 선형 큐, 원형 큐 (0) | 2021.05.06 |