get path in graph

Works for cyclic graph too. Bfs is better than Dfs for large graphs.

graph:
    nodes
node:
    id
    neighbors

Dfs.

// dfs
path-dfs(n1, n2):
    list path, set visited = new 
    path-dfs(n1, n2, path, visited)
    return path

path-dfs(n, n2, path, visited)
    if visited.has(n):
        return false
    path.add(n)
    if n == n2:
        return true
    visited.add(n)
    for neighbor in n.neighbors:
        if path-dfs(neighbor, n2, path, visited):
            return true
    path.removelast()
    return false

Dfs. With a maxdepth limit.

// dfs
path-dfs(n1, n2, maxdepth):
    list path, set visited = new 
    depth = 0
    path-dfs(n1, n2, path, visited, maxdepth, depth)
    return path

path-dfs(n, n2, path, visited, maxdepth, depth)
    if depth > maxdepth || visited.has(n):
        return false
    path.add(n)
    if n == n2:
        return true
    visited.add(n)
    for neighbor in n.neighbors:
        if path-dfs(neighbor, n2, path, visited, maxdepth, depth +1):
            return true
    path.removelast()
    return false

Bfs. With visited and node->parent maps.

// bfs, with node->parent map, multi-threaded also
path-bfs(n1, n2):
    q, visited, parentmap = new
    success = false
    q.enqueue(n1)
    while !q.isempty():
        n = q.dequeue()
        if n == n2:
            success = true
            break
        if visited.has(n):
            continue
        visited.add(n)
        for neighbor in n.neighbors:
            if visited.has(neighbor):
                continue
            parentmap[neighbor] = n //save parent
            q.enqueue(neighbor)
    if !success:
        return null
    return get-path(n2, parentmap)

get-path(n, parentmap):
    path = new
    path.push(n)
    while parentmap.has(n):
        n = parentmap[n]
        path.push(n)
    return path

Bfs. With a maxdepth limit. With visited and node->parent maps. Save depth of node in queue. Or use 2 queues to keep track of depth, one for odd and other for even levels.

path-bfs-maxdepth(n1, n2, maxdepth):
    // maxdepth is > 0
    q, visited, parentmap = new
    success = false
    q.enqueue({ node: n1, depth: 1}) //save depth too
    while !q1.isempty():
        item = q.dequeue()
        n = item.node
        depth = item.depth
        if n == n2:
            success = true
            break
        if visited.has(n):
            continue
        visited.add(n)
        if depth == maxdepth:
            continue
        for neighbor in n.neighbors:
            if visited.has(neighbor):
                continue
            parentmap[nn] = n //save parent
            q.enqueue({ node: nn, depth: depth +1) }) //save depth too
    if !success:
        return null
    return get-path(n2, parentmap)

get-path(n, parentmap):
    path = new
    path.push(n)
    while parentmap.has(n):
        n = parentmap[n]
        path.push(n)
    return path

Tests

graph: 1<->2->3, n1: 1, n2: 3

[Hat tip to ctci]