Graph Search Algorithms

Goals
In this guide, we will learn about graph search algorithms.
Prerequisites
Please have Neo4j (version 4.0 or later) and the Graph Data Science Library downloaded and installed to use graph search algorithms.

Beginner

What are graph search algorithms?

noun Search graph 528032

Graph search (or graph traversal) algorithms explore a graph for general discovery or explicit search. They will try to visit as much of the graph as they can reach, but there is no expectation that the paths they explore are computationally optimal. Graph search algorithms are usually used as a core component of other algorithms.

The Neo4j Graph Data Science Library supports both of the graph search algorithms.

Breadth First Search (BFS) is a graph traversal algorithm that starts from a chosen node and explores all of its neighbors at one hop away before visiting all the neighbors at two hops away, and so on.

While it can be used on its own, it is most commonly used as the basis for other more goal-oriented algorithms. For example, Shortest Path, Connected Components, and Closeness Centrality all use the BFS algorithm. It can also be used to find the shortest path between nodes or for computing the maximum flow in a flow network.

Depth First Search (DFS) is a graph traversal algorithm that starts from a chosen node, picks one of its neighbors, and then traverses as far as it can along that path before backtracking.

Like BFS, DFS can be used on its own, but is more commonly used as a component of other algorithms. For example, Connected Components and Strongly Connected Components use the DFS algorithm. It was originally invented as a strategy for solving mazes and can also be used to generate those mazes.