import { BitField } from "@thi.ng/bitfield/bitfield" ; import { DCons } from "@thi.ng/dcons/dcons" ; import type { IGraph } from "./api.js" ; export class DFS { graph : IGraph ; marked : BitField ; edges : Uint32Array ; src : number ; constructor ( graph , src ) { this . graph = graph ; this . src = src ; const numV = graph . numVertices ( ) ; this . edges = new Uint32Array ( numV ) ; this . marked = new BitField ( numV ) ; this . search ( src ) ; } search ( id ) { const { edges , marked } = this ; marked . setAt ( id ) ; for ( let n of this . graph . neighbors ( id ) ) { if ( ! marked . at ( n ) ) { edges [ n ] = id ; this . search ( n ) ; } } } hasPathTo ( id ) { return this . marked . at ( id ) !== 0 ; } pathTo ( id ) { if ( ! this . marked . at ( id ) ) return ; const { edges , src } = this ; const path = new DCons < number > ( ) ; for ( ; id !== src ; id = edges [ id ] ) { path . cons ( id ) ; } path . cons ( id ) ; return path ; } } param graph param src param dest export const dfs = ( graph , src , dest ) => new DFS ( graph , src ) . pathTo ( dest ) ;