api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 2393
  slug: graph-traversal-algorithms
  title: Graph Traversal Algorithms
  description: Fundamental algorithms for navigating graphs.
  summary: "Algorithms for exploring and searching graphs: breadth-first and depth-first search, Dijkstra, Bellman-Ford, A* and Floyd-Warshall, with bidirectional search, iterative deepening, uniform-cost and greedy best-first search, topological sorting and Johnson's all-pairs algorithm."
  use_when:
    - You need the right traversal or shortest-path algorithm for a graph.
    - You are comparing informed and uninformed search.
  caveats:
    - Choice depends on edge weights, graph size and whether you need one path or all pairs.
    - A* is only optimal when its heuristic is admissible (never overestimates).
  related:
    - graph-algorithms
    - advanced-graph-algorithms
    - backtracking-algorithms
    - search-algorithms
  entry_count: 12
  fields:
    - section: data
      field: name
      type: string
      example: Breadth-First Search
    - section: data
      field: type
      type: string
      example: Traversal
    - section: data
      field: description
      type: string
      example: Explore all neighbors at current depth before d…
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,graphs,traversal
  view_count: 44
  created_at: 1792832553
  updated_at: 1792832553
data:
  - name: Breadth-First Search
    type: Traversal
    description: Explore all neighbors at current depth before deeper vertices.
  - name: Depth-First Search
    type: Traversal
    description: Explore as far as possible along each branch before backtracking.
  - name: Dijkstra
    type: Shortest Path
    description: Greedy shortest path from a source with non-negative edges.
  - name: Bellman-Ford
    type: Shortest Path
    description: Handles negative edge weights and detects negative cycles.
  - name: A* Search
    type: Heuristic Search
    description: Uses a heuristic to guide pathfinding efficiently.
  - name: Floyd-Warshall
    type: All-Pairs Shortest Path
    description: Dynamic programming shortest paths between every pair of vertices.
  - name: Uniform-Cost Search
    type: Shortest path
    description: Expands the lowest-cost path first; equivalent to Dijkstra's algorithm on a graph.
  - name: Iterative Deepening DFS
    type: Traversal
    description: Repeats depth-limited DFS with increasing limits, combining DFS memory use with BFS completeness.
  - name: Bidirectional Search
    type: Shortest path
    description: Searches forward from the start and backward from the goal, meeting in the middle.
  - name: Greedy Best-First Search
    type: Informed search
    description: Expands the node that looks closest to the goal by a heuristic; fast but not guaranteed optimal.
  - name: Topological Sort
    type: Ordering
    description: Orders the nodes of a directed acyclic graph so every edge points forward.
  - name: Johnson's Algorithm
    type: All-pairs shortest path
    description: Reweights edges with Bellman-Ford, then runs Dijkstra from every node; efficient for sparse graphs.