티스토리 뷰
- 아래의 영상을 보고 정리했다.
https://www.youtube.com/watch?v=WbP1KDXLgG4&list=PLrj92cHmwIMfxmffI2RSuSmWfmHvLksoB&index=47
● Graph
1. 그래프의 구성요소
1). 정점(vertex) : 노드의 집합(Tree에서의 노드가 Graph에서는 정점이라고 불린다.)
2). 간선(edge) : 정점 쌍의 집합(각 노드 간의 길이라고 생각하면 된다.)
- 그래프는 정점과 간선 데이터 모두 저장해야 한다.
2. 그래프 정점과 간선의 예
1). 구글 지도 : 각 위치는 정점으로, 경로는 간선으로 표시
2). 인스타 친구 : 각 사용자는 정점으로, 친구 관계는 간선으로 표시
3). 항공 운송망 : 각 공항은 정점으로, 항로는 간선으로 표시. 이를 바탕으로 가장 빠르거나 가장 저렴한 경로를 계산
2. 그래프의 종류
1). 무방향 그래프(= 양방향 그래프)
- 방향이 없는 간선을 갖는 그래프, 방향이 없기에 양쪽 방향으로 모두 이동할 수 있다.
- 간선의 방향이 없기 때문에 간선(x, y)는 간선(y, x)와 같다.
2). 방향 그래프(= 단방향 그래프)
- 방향이 있는 간선을 갖는 그래프, 방향이 있기에 한쪽 방향으로만 이동할 수 있다.
- 간선의 방향이 있기 때문에 간선(x, y)는 간선(y, x)와 서로 다르다.
ex) 네비게이션이 안내해주는 일방통행 길
3). 가중치 그래프와 비가중치 그래프
- 가중치 그래프 : 간선이 가중치를 갖는 그래프(weighted graph)
- 비가중치 그래프 : 간선에 가중치가 없는 그래프(unweighted graph)
- 비가중치 그래프라고 해서 간선의 가중치가 0 인것이 아니라 모두 동일하게 1 인 것이다.
- 위 그림에서 (서울 ~ 부산)으로 직항으로 가는 길의 (가중치 = 7)이다.
- 이때 (서울 ~ 부산)으로 가는 길 중에 가중치가 낮은 경로를 찾는다면 (서울 ~ 대전 ~ 대구 ~ 부산)의 경로가 나온다.
ex) 가중치가 낮은 경로 = 가격이 저렴한 경로
(3 + 2 + 1 = 6 < 7)
4). 순환 그래프와 비순환 그래프
- 순환 그래프 : 하나 이상의 사이클을 갖는 그래프
- 비순환 그래프 : 사이클이 없는 그래프
● Tree와 Graph
- 아직 Tree를 공부하지는 않았지만 간단하게 비교해보자
- Tree 구조는 단방향 이동만 가능하다.(단일경로만 존재) ex) A노드에서 E노드로 가는 길은 오직 하나
- Graph는 양방향 이동이 가능하다.(다양한 경로 존재) ex) A노드에서 E노드로 가는 길은 여러가지
- Tree 구조는 노드간 경로가 단일경로이기 때문에 노드에 대한 정보만 저장하면 된다.
- 정확히 말해 value 값, left 주소값, right 주소값만 저장하면 된다.(여기서 value는 노드에 대한 정보를 의미한다.)
- 그에 반해 Graph는 노드간의 경로가 다양하기 때문에 노드에 대한 정보와 함께 간선에 대한 정보도 저장해야 한다.
cf)
- 위의 그림을 기준으로 A노드는 B노드와 C노드로 갈 수 있는 간선이 있다.
- 위의 그림을 기준으로 B노드는 A노드와 C노드, D노드로 갈 수 있는 간선이 있다.
● Graph 구현 방식
1. 2차원 배열로 구현(adjacency matrix)
2. 연결 리스트로 구현(adjacency list)
1. 2차원 배열로 구현(adjacency matrix)
- 각 노드간 경로가 없으면 0, 경로가 있으면 각 간선의 가중치로 채워진다.
- N개의 정점을 가진 그래프의 이차원 배열의 크기는 N * N 으로 생성한다.
- 희소 그래프(간선의 수가 적은 그래프)의 경우 메모리가 낭비된다.
- 간선의 조회, 추가, 제거에는 O(1)의 시간이 걸린다. 공간 복잡도는 O(n^2)이다.
- 위의 그림은 비가중치 그래프 & 무방향 그래프(양방향 그래프)를 나타낸 것이다.
- 그렇기에 오른쪽 표의 전체 합은 (간선 개수 * 2 = 8)이다.
- 비가중치 그래프에서 간선의 가중치는 모두 1 이다.
- 위의 그림은 정점이 4개이기에 (4*4 = 16바이트)의 메모리를 할당한 상태이다.
- 오른쪽의 표에서 행은 출발점(source), 열은 도착점(destination)을 의미한다.
2. 연결 리스트로 구현(adjacency list)
- 2차원 배열로 구현하는 것의 단점을 보완, 공간(메모리)의 낭비를 막으며 효율적으로 그래프를 저장하는 방법
- 각 정점은 배열에 저장하고 간선의 가중치는 연결 리스트의 노드에 저장한다.
- adjacency list는 희소 그래프(간선의 수가 적은 그래프)를 표현하는데 좋다.
- 위 그림을 기준으로 정점이 4개이기에 (length = 4)인 배열을 선언한 후 각 정점에서 갈 수 있는 정점들을(= 간선들을) 연결리스트로 묶는다.
'CS > 자료구조 및 알고리즘' 카테고리의 다른 글
| #13 이진 탐색(이진 검색, Binary Search) with 재귀함수 (0) | 2023.07.21 |
|---|---|
| #11 삽입정렬(Insertion Sort) (0) | 2023.03.07 |
| #10 선택정렬(Selection sort) (0) | 2023.03.04 |
| #9 버블정렬(Bubble Sort) (0) | 2023.02.23 |
| #8 해시테이블 - 개념(해시, 해시 함수) / ChatGPT 사용해봄 (1) | 2023.02.20 |
- Total
- Today
- Yesterday
- SQL
- 자료구조
- git
- Stream
- API
- 코테
- db
- spring
- 운영체제
- java
- Phaser
- 빅데이터
- Advanced Stream
- 코딩테스트
- OS
- DART
- Phaser3
- MongoDB
- 메모리
- 프로그래머스
- nosql
- MySQL
- Java8
- 알고리즘
- jpa
- 프로세스
- 빅데이터 분석기사
- Spring Boot
- node.js
- SpringBoot
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |