declare function local:depth-first(
  $graph as element(graph),
  $start as xs:integer
) as item()* {
  let $map :=
    local:depth-first(
      $graph,
      $start,
      map{ 'visited':=(), 'payload':=() }
    )
  return $map('payload')
};

declare function local:depth-first(
  $graph as element(graph),
  $current as xs:integer,
  $state as map(*)
) as map(*) {
  let $node := $graph/node[@id = $current]
  return fold-left(
    function($state, $child) {
      let $id as xs:integer := $child/@idref
      return if($id = $state('visited')) then $state
        else local:depth-first($graph, $id, $state)
    },
    map{
      'visited':=($state('visited'), $current),
      'payload':=($state('payload'), $node/@name/string())
    },
    $node/child
  )
};

local:depth-first(
  <graph>
    <node name='Frankfurt' id='1'>
      <child idref='2' />
      <child idref='3' />
      <child idref='4' />
    </node>
    <node name='Mannheim' id='2'>
      <child idref='1' />
      <child idref='6' />
    </node>
    <node name='Würzburg' id='3'>
      <child idref='1' />
      <child idref='7' />
      <child idref='8' />
    </node>
    <node name='Stuttgart' id='4'>
      <child idref='8' />
    </node>
    <node name='Kassel' id='5'>
      <child idref='1' />
      <child idref='10' />
    </node>
    <node name='Karlsruhe' id='6'>
      <child idref='2' />
      <child idref='9' />
    </node>
    <node name='Erfurt' id='7'>
      <child idref='3' />
    </node>
    <node name='Nürnberg' id='8'>
      <child idref='3' />
      <child idref='4' />
      <child idref='10' />
    </node>
    <node name='Augsburg' id='9'>
      <child idref='6' />
      <child idref='10' />
    </node>
    <node name='München' id='10'>
      <child idref='5' />
      <child idref='8' />
      <child idref='9' />
    </node>
  </graph>,
  10
)