# Source code for algorithms.searching.depth_first_search

"""
Depth First Search
------------------
Recursive implementation of the depth first search algorithm used to
traverse trees or graphs. Starts at a selected node (root) and explores the
branch as far as possible before backtracking.
Time Complexity: O(E + V)
E = Number of edges
V = Number of vertices (nodes)
Pseudocode: https://en.wikipedia.org/wiki/Depth-first_search
"""
[docs]def dfs(graph, start, path=[]):
"""
Depth first search that recursively searches the path. Backtracking occurs
only when the last node in the path is visited.
:param graph: A dictionary of nodes and edges.
:param start: The node to start the recursive search with.
:param path: A list of edges to search.
:rtype: A boolean indicating whether the node is included in the path.
"""
if start not in graph or graph[start] is None or graph[start] == []:
return None
path = path + [start]
for edge in graph[start]:
if edge not in path:
path = dfs(graph, edge, path)
return path