Graph Search Algorithms
|
Important - page not maintained
This page is no longer being maintained and its content may be out of date. For the latest guidance, please visit the Neo4j Graph Data Science Library . |
In this guide, we will learn about graph search algorithms.
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?
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
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
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.