DepthFirst Search
Essentially, DFS explores a single path and deep as it can before starting a new path.

1 Choose an arbitrary vertex and mark it visited.

2 From the current vertex, proceed to an unvisited, adjacent vertex and mark it visited.

3 Repeat 2nd step until a vertex is reached which has no adjacent, unvisited vertices (deadend).

4 At each deadend, backtrack to the last visited vertex and proceed down to the next unvisited, adjacent vertex.

5 The algorithm halts there are no unvisted vertices.
Adjacency matrices:O(V^{2})
It is a graph traversal, so we need to iterate over all vertices (V of these). For each vertex, we need to check the neighbours of it. For the matrix represenation, the only way we can guranatee to find all neighbours of vertex i is to do a linear scan across its row in the matrix, which has V elements. So V * V gives O(V2)complexity. The traversal also needs to setup visited status, which requires OV  complexity, but the quadratic term dominates.Adjacency lists:O(V+E)
Similarly to the matrix representation, we need to iterate over all the vertices (V of these). For each vertex, we need to check the neighbours of it. Different for the adjacency list represenation, we only need to scan through the elements in the associated linked list. The total number of elements across all the linked list (and total number of neighbours to consider) is O(E). The traversal also needs to setup visited status, which requires OV  complexity. Hence the total is O(V + E).BreadthFirst Search

1 Choose an arbitrary vertex v and mark it visited.

2 Visit and mark (visited) each of the adjacent (neighbour) vertices of v in turn.

3 Once all neighbours of v have been visited, select the first neighbour that was visited, and visit all its (unmarked) neighbours.

4 Then select the second visited neighbour of v, and visit all its unmarked neighbours.

5 The algorithm halts when we visited all vertices.
DFS  BFS  
Application  Connectivity, Acyclicity  Connectivity, Acyclicity, Shortest paths 
Efficiency for adjacency matrix  Θ(V^{2})  Θ(V^{2}) 
Efficiency for adjacency list  Θ(V + E)  Θ(V + E) 