정점 집합 V와 이들 사이에 존재하는 간선집합 E로 구성된 그래프 G를 보통 G = (V, E)로 표시한다.
정점의 총 수 |v|는 흔히 소문자 n으로 표기한다.
정점 u와 정점 v를 잇는 간선은 관행적으로 {u, v}는 주로 무방향 간선을, (u,v)는 방향 간선을 나타낼 때 쓰인다.
그래프의 표현
1) 인접 행렬
n x n 행렬을 준비하고, 정점 i 와 정점 j 사이에 간선이 있으면 행렬 (i, j)원소, (j, i) 원소 값을 1로 할당한다. 나머지 자리에는 0을 할당한다.(무방향 그래프, 가중치가 없는 경우)
가중치가 있는 경우 행렬의 각 원소에 1 대신 가중치를 저장한다.
정점 i에서 정점 j로 향하는 방향이 있는 간선일 경우 (방향 그래프일 경우) 행렬(i, j)에 값을 (1 또는 가중치) 할당한다.
간선의 밀도가 아주 높은 그래프에서는 인접 행렬 표현이 적합하다.
2) 인접 리스트
간선의 밀도가 아주 높은 경우라면, 인접 리스트 표현법은 그리 적합하지 않다.
3) 인접 배열
그래프는 대부분 정적이기 때문에 연결리스트 대신 배열을 사용하면 효율적이다.
배열을 정렬된 형태로 만들면 이진 탐색을 쓸 수 있어 임의의 정점에 인접한 정점 수가 k라면 lower(log2(k))+1 번 이내의 비교로 j의 존재를 확인할 수 있다.
각 정점의 인접 배열 헤더에 인접 정점이 몇 개인지 표시해 두면 쉽게 탐색할 수 있다.
공간을 깔끔하게 사용하기 위해 하나의 배열을 할당 받아,
각 헤더에 자신의 인접 배열이 끝나는 자리를 표시해 사용할 수도 있다.
4) 인접 해시 테이블
해시 테이블을 위한 공간을 할당 받을 때도 정점 별로 따로 할당 받을 수도 있고,
하나의 배열에 인접 배열 전체 크기의 2배를 할당 받아 나누어 쓸 수도 있다.
DFS (Depth First Search) : 깊이 우선 탐색
DFS는 아래로 갈 수 있는 데까지 갔다가 막히면 되돌아 와서 다시 내려간다.
DFS에 기반한 탐색 방법을 백트래킹으로 통칭하기도 한다.
BFS(Breadth First Search) : 너비 우선 탐색
BFS는 옆으로 쭉 훌터 나가면서 값을 탐색한다.
