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()
testDfs
awaits the calldfs(
yetdfs
will resolves before the search has completed. If any of theawaits
, ievisit
,previsit
,postvisit
are delayed thendfs
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 arraygraph
, Can you provide an example using a tree? BTW Worst case DFS is O(n), your use of arrayvisited
makes it O(n^2) wheren = verts + edges
\$\endgroup\$ – Blindman67 Dec 12 '19 at 15:03dfs()
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\$ – Evgeny Dec 12 '19 at 17:41graph
.(You dont await promise all, andedges(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 provideedges
touches every vert every iteration. Can you provide example that follows edges. \$\endgroup\$ – Blindman67 Dec 12 '19 at 20:16