그래프(Graph)
그래프(Graph)는 정점들이 간선들을 통해 연결된 자료 구조이다. 여러 개의 고립된 부분 그래프들(Isolated Subgraphs)로 구성될 수 있다.
1) 무방향 그래프(Undirected Graph) VS 방향 그래프(Directed Graph)
무방향 그래프는 간선으로 이어진 양쪽 정점 모두 상대편 정점으로 이동할 수 있다.
방향 그래프는 방향성이 존재하여 화살표 방향으로만 이동할 수 있다.
2) 가중치 그래프(Weighted Graph)
가중치 그래프는 간선에 가중치가 할당된 그래프로 '네트워크(Network)'라고도 한다.
3) 연결 그래프(Connected Graph) VS 비연결 그래프(Disconnected Graph)
연결 그래프는 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 그래프이다.
비연결 그래프는 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다.
4) 사이클(Cycle) VS 비순환(Acyclic) 그래프
사이클은 단순 경로의 시작 정점과 종료 정점이 동일한 경우이다.
비순환 그래프는 사이클이 없는 그래프이다.
5) 완전 그래프(Complete Graph)
완전 그래프는 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프로, 무방향 완전 그래프이다.
정점 수가 n개이면 간선의 수는 n * (n-1) / 2이다.
※ 참고 블로그
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
'자료구조' 카테고리의 다른 글
| 자료구조의 소개(자료구조, 알고리즘, 데이터 추상화) (0) | 2023.04.10 |
|---|---|
| 세그먼트 트리(Segment Tree) 자료구조 (0) | 2023.02.04 |
| 해시 테이블(HashTable) (0) | 2022.12.30 |
| 트리(Tree)와 힙(Heap) (0) | 2022.12.30 |
| 스택(Stack)과 큐(Queue) (0) | 2022.12.29 |