Graph Search
Definition
Graph search finds nodes or connections by an algorithm examining relationships in a graph.
A graph consists of nodes and edges. In search, a strategy determines which reachable nodes are examined next: Breadth-first search proceeds level by level, depth-first search first follows a branch deeply.
Simply explained
Imagine a network of roads. You can first check all direct neighboring towns or follow one path further. The comparison explains the order, not the choice of the best route.
Why it matters in practice
The choice of a search method depends on the question and the structure of relationships. The order of exploration is part of the method.
Example from business
Possible example: A company investigates which facilities are connected to a component via multiple supply relationships.
Limits and pitfalls
- A found path is not automatically the shortest or cheapest. Search goal, edge properties, and handling of already visited nodes must be defined.
Origin & history
NIST documents breadth-first and depth-first search as different search strategies. The consulted lexicon entries were updated in 2019 and 2021 respectively; this does not imply an invention date for graph search.
Use in mid-sized companies
- It is conceivable to investigate dependencies in a supply chain. It must be defined in advance what relationship an edge represents and when the search ends.
Frequently asked questions
Are breadth-first search and depth-first search the same?
No. They differ in the order of examined nodes.
Does every graph search deliver the best path?
No. That depends on the method, search goal, and evaluation of edges.
Sources
- breadth-first search · Paul E. Black (2019): breadth-first search
- depth-first search · Paul E. Black (2021): depth-first search
Editorially reviewed on: