Graph Traversal

A level-order traversal strategy that explores all neighbors of a node before moving to the next depth level.

• Uses a queue data structure (FIFO) to manage the frontier
• Guarantees the shortest path in unweighted graphs
• Ideal for finding connections within a fixed number of hops
• Time complexity: O(V + E) where V is vertices and E is edges

Example: Finding all entities within 2 degrees of separation from a central node in a social network graph.

A traversal strategy that explores as far down a branch as possible before backtracking to explore alternative paths.

• Uses a stack data structure (LIFO) or recursion
• Memory-efficient for deep, narrow graphs
• Commonly used for topological sorting and cycle detection
• Does not guarantee shortest path

Example: Exploring a hierarchical ontology from a broad category down to the most specific leaf node before considering sibling branches.

An optimization technique that runs two simultaneous searches—one forward from the start node and one backward from the target node—until their frontiers intersect.

• Reduces the effective search space by half the diameter
• Significantly faster than unidirectional BFS for point-to-point queries
• Requires the graph to support reverse edge traversal
• Common in knowledge graph pathfinding between two known entities

Example: Finding the shortest relationship chain between two specific entities in Wikidata without exploring the entire graph.

The process of traversing multiple sequential edges to answer complex queries that require chaining facts together.

• Each hop represents traversing one relationship edge
• Enables answering questions like "What drugs target proteins associated with a disease?"
• Relies on path ranking algorithms or learned traversal policies
• Critical for Graph RAG systems that ground LLM responses in structured data

Example: Traversing from a disease node to a gene node, then to a protein node, and finally to a drug node to identify potential treatments.

SPARQL property paths enable declarative traversal patterns within RDF knowledge graphs without writing procedural code.

• rdfs:subClassOf* traverses zero or more subclass edges
• ex:connectedTo+ traverses one or more relationships
• ^ex:hasParent inverts the direction of traversal
• The query engine's optimizer determines the most efficient execution plan

Example: ?s rdfs:subClassOf* dbo:Person retrieves all direct and indirect subclasses of Person in DBpedia.

Algorithms like A search* use heuristic functions to estimate the cost from a node to the target, prioritizing promising paths.

• Combines actual path cost with estimated remaining cost: f(n) = g(n) + h(n)
• Requires a domain-specific heuristic that is admissible (never overestimates)
• Dramatically reduces explored nodes compared to uninformed search
• Used in knowledge graph completion for link prediction tasks

Example: Using embedding similarity as a heuristic to guide traversal toward a target entity in a vector-augmented knowledge graph.