# Depth-First Search in Python - Recursive and Non-Recursive Programming

In my graph algorithms course we have been discussing breadth-first search and depth-first search algorithms and are now transitioning to directed acyclic graphs (DAGs) and topological sorting. In class we discussed one method of topological sorting that uses depth-first search. Before writing an article on topological sorting in Python, I programmed 2 algorithms for doing depth-first search in Python that I want to share. One is a recursive Python function and the other is a non-recursive solution that introduces a `Stack` Data Structure to implement the stack behavior that is inherent to a recursive function. I already coded C# versions of depth-first search and breadth-first search, but I am learning Python along with learning algorithms, so I want to share examples of depth-first search in Python as well.

## Adjacency Matrix an Directed Graph

Below is a simple graph I constructed for topological sorting, and thought I would re-use it for depth-first search for simplicity. I am representing this graph in code using an adjacency matrix via a Python Dictionary.

```adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}```

## Depth-First Search Recursive Function in Python

Given the adjacency matrix and a starting vertex of 1, one can find all the vertices in the graph using the following recursive depth-first search function in Python.

```def dfs_recursive(graph, vertex, path=[]):
path += [vertex]

for neighbor in graph[vertex]:
if neighbor not in path:
path = dfs_recursive(graph, neighbor, path)

return path

adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}

# [1, 2, 4, 6, 7, 5, 3]```

I included the variable, `path`, for 2 reasons. First, it is keeping a list of vertices already visited so that the function does not visit a vertex twice. Second, it shows the path that the depth-first search algorithm took to find all the vertices. Since we are using a `list` as opposed to a `set` in Python to keep track of visited vertices, the search to see if a vertex has already been visited has a linear runtime as opposed to constant runtime. I did that for simplicity, but I wanted to mention it.

Notice how the depth-first seach algorithm dives deep into the graph and only backtracks when it comes to a deadend. It dives deep going from 1 -> 2 -> 4 -> 6 -> 7, and then backtracks to go from 2 -> 5, and then backtracks again to go from 1 -> 3.

## Depth-First Search Non-Recursive Function in Python

The Python code for the non-recursive depth-first function is similar to the recursive function, except that a `Stack` Data Structure is necessary to provide the stack functionality inherently present in the recursive function.

```def dfs_iterative(graph, start):
stack, path = [start], []

while stack:
vertex = stack.pop()
if vertex in path:
continue
path.append(vertex)
for neighbor in graph[vertex]:
stack.append(neighbor)

return path

adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}

The path taken is different because the vertices are pushed onto the `Stack` Data Structure in a different order. In this case, the depth-first search function dives deep to the right 1 -> 3 -> 5 -> 6 -> 7, and then backtracks to go from 1 -> 2 -> 4.