- 그래프의 종류
- 무
방향 그래프 : 정점 사이에 방향성이 없는 간선으로 연결된 그래프
(V1,V2) = (V2,V1)
- 방향
그래프 : 간선이 화살표로 표현되어 방향성을 가지는 그래프 <V1,V2)
!= <V2,V1>
- 연결
그래프 : 모든 정점에서 다른 모든 정점으로 경로가 있음
- 약
연결 그래프 : 방향을 제거하면 연결그래프가 됨
- 강
연결 그래프 : 방향성이 있는 연결그래프
- 완전그래프
: 두 쌍의 모든 정점 사이에 간선이 있는 그래프
- 방향그래프 간선의
수 n(n-1)
- 무방향 그래프
간선의수 n(n-1)/2
A(i, j) |
1
|
Vi와 Vj 가 인접한 경우 즉, 두 정점간에 연결선이 존재하는 경우
|
|
0
|
두 정점간에 연결선이 없는 경우 |
- 무방향 그래프의
인접 행렬은 대칭,
방향 그래프의 인접행렬은
대칭이 아닐 수도
있음
- 인접 리스트
: 각 정점에 인접된 정점의 연결 리스트
- 깊이 우선 탐색, 나비 우선 탐색 시 탐색 순서 결정
|
|