Search those graphs up and down until your value has been found!

Graph Search: Conceptual


What if you don't need to find a path, but you _do_ need to get a list of all the values in a graph? 

Well, it turns out that in addition to path-finding, depth-first search is pretty adept at organizing vertices (or vertex values) with a clear order of visitation from beginning to end. 

There are three main traversal orders that you'll come across for graph traversal: 
- _Preorder_, in which each vertex is added to the "visited" list and added to the output list BEFORE getting added to the stack
- _Postorder_, in which each vertex is added to the "visited" list and added to the output list AFTER it is popped off the stack
- Reverse Post-Order (also known as _Topological Sort_), which returns an output list that is exactly the reverse of the post-order list

Take a look at the directed graph structure we have depicted here. Let's say that we want a list of all vertex values, starting with "Lasers", in the order that they are added to the stack.

A pre-order DFS traversal would come in handy and we might end up with the following list. (We'll assume here that this algorithm prefers visiting things in alphabetical order if there is a choice.):
```
["Lasers", "Lava", "Snakes", "Spikes", "Piranhas"]
```

Now, let's say we want the same values, but with each value only added to the list once its vertex has been popped from the stack. In this case, our post-order DFS traversal would result in a list that looked like:

```
["Spikes", "Snakes", "Lava", "Piranhas", "Lasers"]
```

You may notice that the post-order list is not the reverse of the pre-order list. A reverse post-order list would still begin with "Lasers", but then begin to differ:

```
["Lasers", "Piranhas", "Lava", "Snakes", "Spikes"]
```

What happens if there are unvisited vertices that are not reachable from the current path? The search would visit them in (here alphabetical) order after exploring the current path.

Graph Search Traversal Order


You've learned a bunch about graph searches and how to use them effectively:
- You can use a graph search algorithm to traverse the entirety of a graph data structure to locate a specific value
- Vertices in a graph search include a "visited" list to keep track of whether or not each vertex has been checked 
- Depth-first search (DFS) and breadth-first search (BFS) are two common approaches to graph search
- The runtime for graph search algorithms is O(vertices + edges)
- DFS, which employs either recursion or a stack data structure, is useful for determining whether a path exists between two points
- BFS, which generally relies on a queue data structure, is helpful in finding the shortest path between two points
- There are three common traversal orders which you can apply with DFS to generate a list of all values in a graph: pre-order, post-order, and reverse post-order



Graph Search Conceptual Review


Using graphs to model complex networks is pretty swell, but one way that graphs can really come in handy is with _graph search_ algorithms. You can use a graph search algorithm to traverse the entirety of a graph data structure in search of a specific vertex value.

There are two common approaches to using a graph search to progress through a graph:
- depth-first search, known as _DFS_ follows each possible path to its end
- breadth-first search, known as _BFS_ broadens its search from the point of origin to an ever-expanding circle of neighboring vertices

To enable searching, we add vertices to a list, _visited_. This list is pretty important because it keeps the search from visiting the same vertex multiple times! This is particularly vital for cyclical graphs where you might otherwise end up in an infinite loop.

So how do you calculate the runtime for graph search algorithms?

In an upper bound scenario, we would be looking at every vertex and every edge. Because of this, the big O runtime for both depth-first search and breadth-first search is O(vertices + edges).



Graph Search Conceptual Introduction


You're back in a car, but this time, your friend "B" is navigating. Unlike D, B is a bit hesitant about whether you've gone the right way and keeps checking in to see if you are on the best path. At each intersection, B tries out each possible route one by one, but only for a block in each direction to see if you've found your destination.

Like B, breadth-first search, known as _BFS_, checks the values of all neighboring vertices before moving into another level of depth.

This is an incredibly inefficient way to find just _any_ path between two points, but it's an excellent way to identify the _shortest path_ between two vertices. Because of this, BFS is helpful for figuring out directions from one place to another.

Unlike DFS, BFS graph search implementations use a queue data structure to keep track of the current vertex and vertices that still have unvisited neighbors. In BFS graph search a vertex is dequeued when all neighboring vertices have been visited.



Breadth-First Search (BFS) Conceptual


Imagine you're in a car, on the road with your friend, "D." D is on a mission to get to your destination by process of elimination. D won't stop and ask for directions. D just sticks to a chosen path until you reach the end. 

At that point, if the end wasn't actually your destination, D brings you back to the last point when there was an intersection and tries another path. 

Like your friend D, depth-first search algorithms check the values along a path of vertices before moving to another path.

While this isn't exactly ideal when you want to find the shortest path between two points, DFS can be very helpful for determining _if_ a path even exists.

In order to accomplish this path-finding feat, DFS implementations use either a stack data structure or, more commonly, recursion to keep track of the path the search is on and the current vertex. 

In a stack implementation, the most recently added vertex is popped off the stack when the search has reached the end of the path. Meanwhile, in a recursive implementation, the DFS function is recursively called for each connected vertex.

