-----

그래프의 종류

무 방향 그래프 : 정점 사이에 방향성이 없는 간선으로 연결된 그래프 (V1,V2) = (V2,V1)
방향 그래프 : 간선이 화살표로 표현되어 방향성을 가지는 그래프 <V1,V2) != <V2,V1>
연결 그래프 : 모든 정점에서 다른 모든 정점으로 경로가 있음
약 연결 그래프 : 방향을 제거하면 연결그래프가 됨
강 연결 그래프 : 방향성이 있는 연결그래프
완전그래프 : 두 쌍의 모든 정점 사이에 간선이 있는 그래프

방향그래프 간선의 수 n(n-1)
무방향 그래프 간선의수 n(n-1)/2

그래프의 용도

여객기의 항로, 버스의 노선, 판매원의 경로

그래의 표현 방법

인접 행렬(adjacent matrix) : 그래프를 구성하는 각 정점들간의 인접여부를 n * n 의 2차원 배열로 표현한 것.

A(i, j)	1	V_i와 V_j 가 인접한 경우 즉, 두 정점간에 연결선이 존재하는 경우
A(i, j)	0	두 정점간에 연결선이 없는 경우

무방향 그래프의 인접 행렬은 대칭, 방향 그래프의 인접행렬은 대칭이 아닐 수도 있음

인접 리스트 : 각 정점에 인접된 정점의 연결 리스트

깊이 우선 탐색, 나비 우선 탐색 시 탐색 순서 결정