그래프 G = (V, E)를 표현하는 표준 방법에는 인접 리스트와 인접 행렬, 두 가지 방법이 있다. 두 가지 모두 방향 및 무방향 그래프에 적용할 수 있다. 하지만 인접 리스트 방법이 희소 그래프에 대해 훨씬 효율적이기 때문에 일반적으로 많이 사용한다. 그리고 희소하다는 것은 ｜E｜ = ｜V｜^2보다 훨씬 작음을 의미한다. 하지만, ｜E｜값이 ｜V｜^2과 거의 비슷한, 조밀한 그래프일 경우, 또는 주어진 두 정점을 연결하는 간선이 있는지를 빠르게 확인할 필요가 있을 때는 인접 행렬 표현법이 더욱 선호되기도 한다.
그래프 탐색 기법은 너비 우선 검색과 깊이 우선 검색이 있다. 너비 우선 검색은, 주어진 그래프 G = (V, E)와 구별되는 출발점(source) s에 대해, 너비 우선 검색은 s로부터 닿을 수 있는 모든 정점을 발견해서, G의 간선들을 체계적으로 검색한다. 이것은 s에서 닿을 수 있는 정점까지의 각 거리(가장 작은 간선의 수)를 계산한다. 또한 s를 루트로 가지괴 s에서 닿을 수 있는 모든 정점을 가지는 너비 우선 트리를 만들어 낸다. s에서 닿을 수 있는 모든 정점 v에 대해 너비 우선 트리의 s에서 v까지의 경로는 그래프 G의 s에서 v까지의 최단 경로와 같다. 즉, 가장 적은 수의 간선을 포함한 경로다. 이 알고리즘은 방향, 무방향 그래프 모두에 적용된다.
너비 우선 검색은 발견된 것과 발견되지 않은 정점들 사이에 있는 경계선(frontier)의 너비를 가로질러 고르게 확장해 나가므로 이름이 그렇게 지어졌다. 즉, 이 알고리즘은 s에서 거리가 k + 1인 어떤 정점을 찾기 전에 s로부터의 거리가 k인 정점을 모두 찾는 알고리즘이다.
깊이 우선 검색의 전략은, 이름이 암시하는대로, 그래프에서 가능하기만 하면 더 깊이 검색하는 것이다. 깊이 우선 검색에서, 아직 탐사되지 않은 간선을 가진 가장 최근에 발견된 정점 v에서 나오는 간선이 탐사된다. v의 모든 간선들이 탐사되면, 검색은 역행해서 v를 발견하게 해준 정점으로부터 나오는 간선을 탐사한다. 이 과정은 출발점으로부터 도달할 수 있는 모든 정점이 발견될 때까지 계속된다. 만약, 발견되지 않은 정점이 남아있다면, 그 중 하나는 새 출발점으로 선택되고 검색은 그 출발점으로부터 반복된다. 이 전체 과정은 모든 정점이 발견될 때까지 반복된다.
너비 우선 검색에서처럼, 이미 발견된 정점 u의 인접 리스트를 한 번 훑어보는 동안 어떤 정점 v가 발견될 때마다, 깊이 우선 검색은 v의 선행자 항목 π[v]를 u로 정함으로써 이 사건을 기록한다. 선행 부분 그래프가 하나의 트리를 형성하는 너비 우선 검색과는 달리, 깊이 우선 검색에 의해 만들어진 선행 부분 그래프는 여러 개의 트리로 구성될 수 있다. 왜냐하면 이 검색은 여러 출발점들부터 반복될 수 있기 때문이다. 그러므로 깊이 우선 검색의 선행 부분 그래프(predecessor subgraph)는 너비 우선 검색의 정의와는 약간 다르게 정의된다. G(π) = (V, E(π))라고 하고, 여기서,
E(π) = { (π[v], v) : v ∈ V and π[v] ≠ NIL }
이다. 깊이 우선 검색의 선행 부분 그래프는 여러 개의 깊이 우선 트리로 구성된 깊이 우선 포리스트를 형성한다. E(π)에 있는 간선은 트리 간선으로 불린다.
Library/Algorithm