그래프 용어정리
directed graph(단방향) / undirected graph(양방향)
1.
- 정점 V(vertex)
- 간선 E(edge)
- 정점의 부착(incident) 간선
- 정접의 인접(adjacent) 정점
2. 차수(degree) 하나의 정점에 인접한 정점의 수
- 진입차수 : InDegree
- 진출차수: OutDegree
InDegree=OUtDegree
3.
- Path : 경로
- Cycle : 순환경로(재귀)
4. 가중치 그래프(Weighted Graph)
정점과 정점사이의 간선에 가중치가 부여되어있는 그래프
인접행렬에서 그래프 표현
양방향 그래프
- 대각선을 기준으로 Adjacent Matric(인접 행렬)을 그렸을 때 대칭한다.
- 간선의 개수를 통해 차수를 알수있다.
- python_append() 함수를 통해서 대칭인 부분을 한번에 표현가능
일방향 그래프
- 인접행렬을 통해 InDegree와 OutDegree개수를 확인할 수 있다.
가중치 그래프
- 양방향 그래프의 성질과 같음
'취준일기' 카테고리의 다른 글
| [TIL_알고리즘] 재귀호출(Recursion) (0) | 2020.11.16 |
|---|---|
| [TIL_알고리즘] 완전 탐색 DFS(Depth First Search) (0) | 2020.11.15 |
| [TIL_알고리즘] 정렬 알고리즘 Counting Sort (0) | 2020.11.13 |
| 11/12 일지 (0) | 2020.11.12 |
| [TIL_알고리즘] 정렬 알고리즘 Selection Sort (0) | 2020.11.12 |