Join egghead, unlock knowledge.

Want more egghead?

This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock This Lesson
1×
Become a member
to unlock all features
Autoplay

    Write a Depth First Search Algorithm for Graphs in JavaScript

    Kyle ShevlinKyle Shevlin
    javascriptJavaScript

    Depth first search is a graph search algorithm that starts at one node and uses recursion to travel as deeply down a path of neighboring nodes as possible, before coming back up and trying other paths.

    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Transcript

    Transcript

    Instructor: 00:00 As the name implies, depth first search is a graph search algorithm that explores as far as it can down a particular path before climbing back up and working down another one. We'll add a depth first search method to our graph object.

    00:14 This method will receive two arguments, a starting node key to find which node in the graph to start the search from and a visiting function to be called as we visit each node for the first time. First, we need to get the starting node by using the get node method.

    00:30 Next, we need to keep track of which nodes we have visited and which ones we haven't. There are several ways we can do this, but I'm going to do it by keeping a visited object where each key corresponds with a node's key, and the value starts as false. Now, depth first search involves a recursive algorithm.

    00:49 Essentially, if there's another level to go down, we need to explore that one until we reach a dead end. I'm going to create an explore function that we will call on our nodes. If we visited this node, then return from the function immediately.

    01:04 Otherwise, call the visiting function on the node and mark it as visited. Next, we want to loop through each of this node's neighbors and call explore on them. Lastly, we start our algorithm by calling explore on our starting node. Now that we've created our depth first search algorithm, let's use it.

    01:24 I've pre-made a graph that I'll copy paste into the file that looks like this. I want to call depth first search on our graph starting at node A and logging out each key as we go. If I bring the graph back onto the screen and we call our search in the terminal, we could see that we went as far down the path of A we could before we climbed back up and went down another path.

    Discuss

    Discuss