# DFS – Depth-First search algorithm

Date: April 24, 2020

Categories: Algorithms

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