5
\$\begingroup\$

I implemented a general function for a depth-first-search (DFS) using JavaScript with default arguments and functions that need to be provided in order for it to work.

This function is using async & await, but both can be removed to make it synchronous.

  • Is the naming sensible?
  • Are there missing pieces that would be useful for a general DFS?
  • Any other improvements/suggestions/problems with this code?

async function dfs(
  v         = null,         // vertex `v` for the DFS starting point
  visited   = (v) => false, // function: return true/false if `v` was visited
  visit     = (v) => {},    // function: mark v as visited
  edges     = (v) => [],    // function: return list of vertices reachable from `v`
  previsit  = (v) => {},    // callback called before visiting edges
  postvisit = (v) => {},    // callback called after visiting edges
) {
  await previsit(v)
  await visit(v)
  Promise.all(
    edges(v).map(async (w) => {
      if (!visited(w))
        return await dfs(w, visited, visit, edges, previsit, postvisit)
    })
  )
  await postvisit(v)
}

async function testDfs() {
  const graph = [ // basic adjacency list graph
    { 'id': 'r', 'edges': ['a','b','c'] },
    { 'id': 'a', 'edges': ['b'] },
    { 'id': 'c', 'edges': ['r', 'a'] },
    { 'id': 'b', 'edges': ['d'] },
    { 'id': 'd', 'edges': [] },
  ]
  const visited = [] // list of visited vertex ids
  await dfs(
    graph[0],
    v => visited.includes(v.id),
    v => visited.push(v.id),
    v => graph.filter(w => v['edges'].includes(w.id)),
    v => console.log(' pre', v.id),
    v => console.log('post', v.id)
  )
}

testDfs()

\$\endgroup\$
3
  • \$\begingroup\$ There are some issues making this question borderline off topic. The test function testDfs awaits the call dfs( yet dfs will resolves before the search has completed. If any of the awaits, ie visit, previsit, postvisit are delayed then dfs will resolve after first vert and there is a good chance that some verts will be visited more than once. Also DFS searches trees, your example is RELIANT on the array graph, Can you provide an example using a tree? BTW Worst case DFS is O(n), your use of array visited makes it O(n^2) where n = verts + edges \$\endgroup\$ Commented Dec 12, 2019 at 15:03
  • \$\begingroup\$ @Blindman67 thank you for the review. How does dfs() resolve before visiting all nodes? I don't seem to understand the use case you are describing. Regarding your "dfs is for trees-only" comment, that is simply not true. DFS doesn't search just trees, a tree is one type of graph, but there are many types of graphs and DFS searches any graph by visiting all of its vertices - works just fine with cyclic graphs as well (which are not trees). \$\endgroup\$ Commented Dec 12, 2019 at 17:41
  • \$\begingroup\$ The early return is very dependent on JS context state and the state of graph.(You dont await promise all, and edges(v).map(async (w) => {if (!visited(w) is wrong as !visited(w) is not async). Semantics (tree/tree like/graph) A DFS searches by following edges and avoids (does not touch) unreachable verts. The callback in the example you provide edges touches every vert every iteration. Can you provide example that follows edges. \$\endgroup\$ Commented Dec 12, 2019 at 20:16

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.