Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Pseudocode

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

Python Implementation

class GraphTraversals:
  def __init__(self, graph):
    self.graph = graph

  def __str__(self):
    return str(self.graph)

  def dfs(self, source):
    self.visited = []
    self.__dfs__(source)
    return self.visited

  def __dfs__(self, source):
    self.visited.append(source)
    if len(self.graph[source]) == 0:
      return # base case
    
    for node in self.graph[source]:
      if node not in self.visited:
        self.__dfs__(node)

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

g = GraphTraversals(graph)
print(g.dfs('A'))