ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Recursive Graph Pathfinding (DFS)

SQL PostgreSQL

Goal -- WPM

Ready
Exercise Algorithm Area
1WITH RECURSIVE graph_paths AS (

2-- Base case: Start at the source node

3SELECT

4start_node,

5target_node,

6ARRAY[start_node] AS path,

70 AS depth

8FROM

9edges

10WHERE

11start_node = 'A' -- Specify your starting node here

12

13UNION ALL

14

15-- Recursive step: Explore neighbors

16SELECT

17gp.start_node,

18e.target_node,

19gp.path || e.target_node,

20gp.depth + 1

21FROM

22graph_paths gp

23JOIN

24edges e ON gp.target_node = e.start_node

25WHERE

26-- Prevent cycles: Ensure the next node is not already in the current path

27NOT (e.target_node = ANY(gp.path))

28AND gp.depth < 10 -- Limit recursion depth to prevent infinite loops in cyclic graphs

29)

30SELECT

31start_node,

32target_node,

33path

34FROM

35graph_paths

36WHERE

37target_node = 'E'; -- Specify your target node here
Algorithm description viewbox

Recursive Graph Pathfinding (DFS)

Algorithm description:

This SQL query uses a recursive Common Table Expression (CTE) to find all possible paths from a specified start node to a target node in a graph. The graph is represented by an `edges` table with `start_node` and `target_node` columns. It's suitable for scenarios like finding routes in a network or tracing dependencies. The query includes basic cycle detection and depth limiting.

Algorithm explanation:

The recursive CTE `graph_paths` starts with the base case: all edges originating from the `start_node`. The recursive step then joins the current paths with edges where the `target_node` of the current path matches the `start_node` of a new edge. It appends the new `target_node` to the path and increments the depth. Cycle detection is achieved by checking if the `e.target_node` is already present in `gp.path`. A depth limit (`gp.depth < 10`) is imposed to prevent infinite recursion in graphs with cycles. Time complexity can be exponential in the worst case for dense graphs, but is bounded by the depth limit and graph structure. Space complexity is related to the number and length of paths found.

Pseudocode:

WITH RECURSIVE graph_paths AS (
  -- Base Case:
  SELECT start_node, target_node, [start_node] AS path, 0 AS depth
  FROM edges
  WHERE start_node = 'START_NODE'

  UNION ALL

  -- Recursive Step:
  SELECT gp.start_node, e.target_node, gp.path + [e.target_node], gp.depth + 1
  FROM graph_paths gp
  JOIN edges e ON gp.target_node = e.start_node
  WHERE e.target_node NOT IN gp.path
    AND gp.depth < MAX_DEPTH
)
SELECT start_node, target_node, path
FROM graph_paths
WHERE target_node = 'TARGET_NODE';