Skip to content
Code it · Write it

Write depth-first search

Write dfs_order(graph, start) (Python) or dfsOrder(graph, start) (JavaScript/TypeScript). graph[u] lists the neighbours of node u (one-way graphs list only the edges leaving u), in alphabetical order.

Return the nodes in the order a depth-first search from start first visits them, taking each node’s neighbours in the order graph[u] lists them.

Visit a node, then fully explore each neighbour you haven’t seen yet before moving on to the next one. A recursive helper does this in a few lines: each call is one node, and the calls waiting underneath remember where to come back to.

def dfs_order(graph, start):
    # graph[u] lists u's neighbours. Return the nodes in the order you first visit them.
    order = []
    seen = set()
    return order