728x90
개요
그래프는 정점과 정점을 잇는 간선의 모임이며 데이터의 표현 방식이다.
그래프 자체가 알고리즘이라기 보단, 그래프를 근거로한 여러 알고리즘들이 존재한다.
본문
그래프의 종류
그래프의 집합 표현
V = Vertex
E = Edge
V(G1) = {A, B, C, D}
E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}
V(G3) = {A, B, C, D}
E(G3) = {<A, B>, <A, D>, <D, A>}
그래프의 구현
인접 행렬 기반
V*V 크기의 2차원 배열을 사용하여 구현한다.
인접 리스트 기반
연결리스트를 기반으로 그래프를 구현한다.
무방향 그래프의 경우 정점 노드를 둘다 연결해야함에 주의
그래프 탐색 알고리즘
대표적으로 DFS와 BFS가 있다.
- DFS(Depth First Search, 깊이 우선 탐색)
- BFS(Breadth First Search, 너비 우선 탐색)
참고
'알고리즘&자료구조 > 이론' 카테고리의 다른 글
| [알고리즘] 유니온 파인드(Union-FInd) (0) | 2023.02.23 |
|---|---|
| [알고리즘] 두 포인터 (Two Pointers) (1) | 2023.02.15 |
| [알고리즘] DFS와 BFS (0) | 2023.02.02 |
| [자료구조] 트리(Tree) (0) | 2022.10.27 |
| [자료구조] 해시 테이블(Hash Table) (0) | 2022.10.21 |