# DFS – Depth-First search algorithm

Depthfirst 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'))``````