Create Python implementations of depth-first search and breadth-first search algorithms.

Graph Search: Python


You can create a depth-first search function with a stack or with recursion (which employs a _call stack_). The recursive implementation is far more common, so that's how you'll do it here.

Ok, roll up your sleeves and get ready to build the recursive case for your function... 

This part of the function will go something like:

```
loop through each neighbor of the current vertex in the graph:

  if neighbor has not been visited:

    recursively call dfs on neighbor
    
    if a path exists:

      return the path
```

Search It Again, Sam

We don't want to do anything with neighbors that we've already visited, so we'll skip those.
Having narrowed our search down to unvisited neighboring vertices, there are two possibilities:
- The vertex has the value we've been looking for.
- The vertex doesn't have the value we're looking for and so we want to add it to the queue.

Our code will follow this logic:

```
if neighbor has not been visited:

  if neighbor is equal to target_value:
            
    return path including neighbor

  else:

     add neighbor and its path to the queue
```

A Breadth of Fresh Neighbors


Let's dig into our depth-first search function and consider: what do we actually want the algorithm to do for us?

- Find out if a path exists between vertices and return `True` or `False` accordingly?
- Return the distance between origin and destination that we get for the first path the function finds?
- Return the path itself?

We'll go with the third option here, which gives us the other information as well.

The beginning of our depth-first function will look something like this:

```
def dfs(graph, current_vertex, target_value, visited):

  set visited to empty list if not yet set

  add current_vertex to visited
```



A Graph Search with Real Depth


Unlike DFS, BFS is primarily concerned with the *shortest* path that exists between two points, so that's what we'll be thinking about as we build out our breadth-first search function. 

Using a queue will help us keep track of the current vertex and its corresponding path. Unlike with DFS, with BFS we may have to expand on paths in several directions to find the path we're looking for. Because of this, our path is not the same as our visited vertices. 

For `visited` we don't care about the order of visitation; we only care about whether a vertex is visited or not, so we'll use a Python set. Our breadth-first search logic should begin something like this:

```
def bfs(graph, start_vertex, target_value):

  set path to a list containing the start_vertex

  create a queue to hold vertices and their corresponding paths

  define an empty visited set
```

Breadth-First Search: Take My Breadth Away

Time to handle our base case! 

If the current vertex value is the same as the value we are looking for, then: 
- we're done searching
- we can return our path (the `visited` list)

```
# what you've built out so far:
def dfs(graph, current_vertex, target_value, visited): 

  set visited to empty list if not yet set

  add current_vertex to visited

  # base case:
  if current_vertex is equal to target_value:

    return visited list
 
```

Case of Base

Take a look at the two graph search functions you implemented in Python:- depth-first search, using recursion- breadth-first search, using a queue

Graph Search Python: Review

What time is it? Time to build out graph search algorithms in Python!Graph search algorithms can be tremendously helpful for path-finding between different points in a graph data structure. First, you'll build out a _depth-first search_ algorithm using recursion that can help you determine if a path exists and, if so, provide you with the first possible path that the function finds.Then you will build out a _breadth-first search_ function that will lead you to the shortest path between two points.Are you excited? You should be. The power of graph search compels you.It's possible to build graph search functions as class methods within a graph data structure implementation, but here we want to focus on the algorithms themselves. For that reason, our graphs are modeled using a Python dictionary. Within the dictionary, each key-value pair maps a vertex value to a set of that vertex's connected vertex values:```pysome_vertex_value: set([connected_value_1, connected_value_2, connected_value_3])```

A Tale of Two Graph Searches


Phew! That was a lot of definitions at the beginning of our BFS algorithm.

It's time to put those shiny new variables to good use!

Here's the basic plan for what we're doing:

```
  loop through queue while the queue is not empty:

    set current_vertex & path equal to first vertex & path on queue

    add current_vertex to visited set

    loop through each neighbor of current_vertex in graph
```