Graph Search: Swift

So far, we are able to traverse the entirety of the graph. However, just like for our depth-first traversal, there will be a problem if the graph has a cycle.

If a graph contains a cycle, we would get stuck in an infinite loop, continuously iterating over the same neighbors with `queue.enqueue(neighbor)`. To account for this, we can use a `where` statement in the `for-in` loop to ensure that we don't enqueue nodes that we've already visited.


Breadth-First Search (Cyclic)

So far, we are able to traverse the entirety of the graph. However, there will be a problem if the graph has a cycle.

If there was a cycle, for example a path from one vertex to itself, we would be stuck in an infinite loop, continuously iterating over the same neighbors using `stack.append(neighbor)`. To account for this, we can use a `where` statement in the `for-in` loop to ensure nodes are not duplicated.


Depth-First Search (Cyclic)

Now it’s time to focus on breadth-first traversal! As a reminder, the breadth-first traversal iterates through the graph in layers. It goes down one layer, which comprises of the start node's direct neighbors. Then it proceeds down to the next layer, which consists of all the nodes that are neighbors of the nodes in the previous layer.

Instead of using a `stack` to iterate through the nodes, we will use a queue to traverse through the graph. Queues have are first-in first-out (FIFO). This is the appropriate data structure here because all of a node's neighbors will be visited before moving on. The workspace includes the [Queue implementation from an earlier lesson](https://www.codecademy.com/courses/intro-to-algorithms-and-linear-data-structures-in-swift/lessons/queues-swift/exercises/introduction-to-queues).  Note that the function is almost exactly identical to the dfs(startingAt:) method, except that it uses a queue instead of a stack.

Breadth-First Search (BFS)

Welcome back to the Graph data structure! In this lesson, we'll implement graph searching algorithms, also known as traversals.

Traversals are incredibly useful when you are trying to find a particular value or a path in a graph. We’ll first explore the depth-first traversal method for traversing through an acyclic graph. To recap, depth-first traversals iterate down each vertex, one neighbor at a time, before going back up and looking at the neighbor’s connected nodes. In this exercise, we will focus on traversing down the full length of one path and printing each node's data value.

We'll be using the `Graph` structures and classes defined in the [Graphs lesson](https://www.codecademy.com/content-items/f198d95eb82f4bbfac8100d2964eeff3/exercises/introduction-to-graphs?bypass_cache=true&draft=true). 


Depth-First Search (DFS)

Great work! You can now use a variety of tools to traverse and search your graphs. Let's recap the types of graph search functions we've implemented.

- **Depth-First Search** (DFS): DFS explores nodes by starting at a root node and exploring each branch as far as it can. Once a branch is complete, DFS backtracks and searches the next branch.
- **Breadth-First Search** (BFS): BFS explores nodes by starting at a root node and exploring each neighboring node before continuing to each neighboring nodes' child nodes. Once a layer is complete, BFS continues to the next layer.

Let's call our new algorithms on some data and see how they perform!
