In my last post we covered how to implement a graph in javascript.
In this week's post we'll be going over how to traverse through a graph. Similar to our traversal of binary search trees, there are two main methods of traversal that we'll be using. Breadth-first search(BFS) and depth-first search(DFS).
However, for our graph searches we're going to need to keep track of which nodes we've traversed to. If we didn't we could potentially visit the same node multiple times due to nodes in a graph potentially having multiple vertices.
Breadth First Search
For our BFS function we're going to start by creating a visited array and populate it with boolean values for each node in our graph.
We'll then use a queue to keep track of nodes we need to visit and fill it with our starting node.
Then we loop through our queue and view our current node and its edges.
From there we loop through the nodes edges. If we have yet to visit the node we add it to the queue and mark it as visited.
Depth First Search
For our DFS function we're going to utilize a recursive helper function instead of a queue of stack.
We'll start in the same fashion with creating and populating a visited array.
Then we'll pass our node and our visited array into our helper function.
The function will set the node to visited, get its edges, loop through the edges, and pass non visited edges into our recursive function.
Thanks for reading! The code for my graph posts can be found here.
Top comments (0)