graph-search.asc

Graph Search

Graph search allows you to visit search elements.

Warning

Graph search is very similar to [Tree Search & Traversal]. So, if you read that sections some of the concepts here will be familiar to you.

There are two ways to navigate the graph, one is using Depth-First Search (DFS) and the other one is Breadth-First Search (BFS). Let’s see the difference using the following graph.

Depth-First Search for Graphs

With Depth-First Search (DFS) we go deep before going wide.

Let’s say that we use DFS on the graph shown above, starting with node 0. A DFS, will probably visit 5, then visit 1 and continue going down 3 and 2. As you can see, we need to keep track of visited nodes, since in graphs we can have cycles like 1-3-2. Finally, we back up to the remaining node 0 children: node 4.

So, DFS would visit the graph: [0, 5, 1, 3, 2, 4].

Breadth-First Search for Graphs

With Breadth-First Search (BFS) we go wide before going deep.

Let’s say that we use BFS on the graph shown above, starting with the same node 0. A BFS, will visit 5 as well, then visit 1 and will not go down to it’s children. It will first finish all the children of node 0, so it will visit node 4. After all the children of node 0 are visited it continue with all the children of node 5, 1 and 4.

In summary, BFS would visit the graph: [0, 5, 1, 4, 3, 2]

Depth-First Search vs. Breadth-First Search in a Graph

DFS and BFS can implementation can be almost identical; the difference is the underlying data structured. In our implementation, we have a generic graphSearch where we pass the first element to start the search the data structure that we can to use:

DFS and BFS implementation

link:../../../src/data-structures/graphs/graph.js[role=include]

Using an part02-linear-data-structures.asc (LIFO) for DFS will make use keep visiting the last node children while having a part02-linear-data-structures.asc (FIFO) will allow to visit adjacent nodes first and "queue" their children for later visiting.

Tip	you can also implement the DFS as a recursive function, similar to what we did in the DFS for trees.

You might wonder what the difference between search algorithms in a tree and a graph is? Check out the next section.

DFS/BFS on Tree vs Graph

The difference between searching a tree and a graph is that the tree always has a starting point (root node). However, in a graph, you can start searching anywhere. There’s no root.

Note	Every tree is a graph, but not every graph is a tree.