그래프(Graph)
- 실제 세계의 현상이나 사물을 정점Vertex(노드)와 간선Edge으로 표현하기 위해 사용
- 루트 노드, 부모/자식의 개념이 존재하지 않음
용어
- 정점(Vertex)/노드(Node) : 위치
- 간선(Edge)/link/branch : 위치 간의 관계를 표시한 선
- 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점
- 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수
- 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수
- 경로 길이(Path Length) : 경로를 구성하기 위해 사용된 간선의 수
- 단순 경로(Simple Path) : 처음/끝 정점을 제외하고 중복된 정점이 없는 경로
- 사이클(Cycle) : 단순경로에서 시작/종료 정점이 동일한 경우
종류
1. 무방향 그래프(Undirected Graph) : 방향X, 노드의 양방향 이동 가능
* A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)
1-1. 연결그래프(Connected Graph): 모든 노드에 대해 항상 경로가 존재
1-2. 비연결 그래프(Disconnected Graph) : 특정 노드에 대해 경로가 존재하지 않음
2. 방향 그래프(Directed Graph) : 방향O
* A->B가 연결되어 있을 경우 <A,B>
3. 가중치 그래프(Weighted Graph)/네트워크(Network) : 간선에 비용/가중치가 할당
4. 비순환 그래프(Acyclic Graph) : 사이클이 없는 그래프
5. 완전 그래프(Complete Graph) : 그래프의 모든 노드가 서로 연결
728x90
'자료구조 & 알고리즘 & cs > 알고리즘' 카테고리의 다른 글
[TIL] 탐욕 알고리즘 - Greedy Algorithm (0) | 2023.04.05 |
---|---|
[TIL] 그래프- BFS, DFS (0) | 2023.03.27 |
[TIL] 탐색 알고리즘- 이진 탐색, 순차 탐색 (0) | 2023.03.24 |
[TIL] 동적 계획법 - DP, Dynamic Programming (0) | 2023.03.17 |
[TIL] 병합정렬 - Merge Sort (0) | 2023.03.15 |