Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited set prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

On the canonical 6-vertex graph from graph-adjacency-list, starting at vertex 1, the deterministic visit order is [1, 2, 4, 3, 5, 6]. Calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1 after all vertices are visited.

Basic Implementation

basic.sql

.mode list
.headers off
CREATE TABLE edge(u INTEGER, v INTEGER);
INSERT INTO edge(u, v) VALUES
  (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6);

-- Iterative DFS: the recursive CTE carries an explicit stack (space joined),
-- a visited set (comma bounded), and the visit order. Each step pops the
-- front node; if unseen it records the node and pushes its neighbours.
WITH RECURSIVE
adj(u, v, seq) AS (
  SELECT u, v, rowid * 2 - 1 FROM edge
  UNION ALL
  SELECT v, u, rowid * 2 FROM edge
),
dfs(stack, visited, ord) AS (
  SELECT '1', ',', ''
  UNION ALL
  SELECT
    CASE WHEN instr(visited, ',' || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) || ',') > 0
         THEN (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, instr(stack, ' ') + 1) ELSE '' END)
         ELSE TRIM(COALESCE((SELECT GROUP_CONCAT(nbr, ' ') FROM
                (SELECT a.v AS nbr FROM adj a WHERE a.u = (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) ORDER BY a.seq)), '')
               || ' ' || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, instr(stack, ' ') + 1) ELSE '' END)) END,
    CASE WHEN instr(visited, ',' || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) || ',') > 0
         THEN visited
         ELSE visited || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) || ',' END,
    CASE WHEN instr(visited, ',' || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) || ',') > 0
         THEN ord
         WHEN ord = '' THEN (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END)
         ELSE ord || ',' || (CASE WHEN instr(stack, ' ') > 0 THEN substr(stack, 1, instr(stack, ' ') - 1) ELSE stack END) END
  FROM dfs
  WHERE stack <> ''
)
SELECT '[' || REPLACE(ord, ',', ', ') || ']'
FROM dfs
ORDER BY length(ord) DESC, ord DESC
LIMIT 1;

Complexity

Time: O(V + E)
Space: O(V) recursion depth

Implementation notes

SQL: a recursive CTE carries an explicit stack, visited set, and visit order as strings, popping the front node each step.
The replay shows the current vertex, the visited set, and the running visit order after each entry, matching the lesson spec.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.