Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
Tags
- skip ci
- UTXO
- 텍스트 가운데 정렬
- Relational Database
- #유니티
- 블록체인
- Factory 함수
- react
- caverjs
- solidity
- CSS
- 3티어 아키텍처
- javascript
- npm
- 2티어 아키텍처
- Private Blockchain
- #1인게임개발
- Factory Functions
- 안정 정렬
- short-circuiting
- SQL
- IP
- NoSQL
- Hybrid Blockchain
- 명시도
- CLI
- 불안정 정렬
- ES6 모듈
- CSS Specificity
- http 모듈
Archives
- Today
- Total
짹뚜 스튜디오
자료구조: 그래프(Graph) 본문
그래프는 정점 (node 또는 vertice)와 간선 (edge)로 이루어진 자료구조이다. 여기서 노드에는 데이터가 저장되고 엣지는 두 노드 사이의 관계를 나타낸다.
위 그래프에서 노드는 {1, 2, 3, 4, 5} 이고 엣지는 {12, 13, 23, 25, 34, 45}이다.
그래프의 종류에 대해서 알아보자.
- Directed Graph (방향 그래프): 두 노드를 연결하는 엣지의 방향이 존재하는 그래프. 왼쪽 그래프에서 엣지 1->2는 존재하지만 2->1 은 존재하지 않는다. edge(12) ≠ edge(21)
- Undirected Graph (무방향 그래프): 두 노드를 연결하는 엣지의 방향이 없이 양방향으로 연결되는 그래프. 오른쪽 그래프에서 엣지 1->2와 2->1이 같다. edge(12) = edge(21)
- Cyclic Graph: 한 노드에서 출발하여 자기 자신으로 다시 돌아오는 경로가 있는 그래프.
- Acyclic Graph: 한 노드에서 출발하여 자기 자신으로 다시 돌아오는 경로가 없는 그래프.
그래프를 표현하는 방식에는 두 가지가 있다.
- Adjacency Matrix (인접 행렬): 2차원 배열을 사용해서 그래프를 표현한다. 2차원 배열이기 때문에 노드의 수에 제곱만큼의 공간을 차치하지만 구현이 간단하다. 예를 들어, 아래의 그래프처럼 A와 B 사이에 엣지가 있다면 배열에서 [A][B]의 값이 1이 되고 [B][A]의 값도 1이 된다. (Undirected Graph 이기 때문에)
- Adjacency List (인접 리스트): 연결 리스트를 사용해서 그래프를 표현한다. 공간은 노드 수와 엣지의 수를 합한 만큼만 차지하지만 구현이 복잡하다. 예를 들어, 아래의 그래프에서 A 노드와 엣지로 연결된 인접한 노드들이 리스트 형태로 표현된다.
따라서 노드의 수가 적으면 Adjacency Matrix, 많다면 Adjacency List로 구현하는 게 좋다.
'개발 공부 > 알고리즘' 카테고리의 다른 글
이진 탐색 (Binary Search) (0) | 2021.12.06 |
---|---|
그리디(탐욕) 알고리즘 (0) | 2021.11.30 |
트리 순회 알고리즘 (0) | 2021.11.28 |
그래프 탐색 알고리즘: DFS, BFS (0) | 2021.11.25 |
순열/조합 찾기 알고리즘: Next Permutation (0) | 2021.11.20 |
Comments