DFS algorithm for graph search theories.

depth_firth_search.py

def recursive_dfs(v, discovered=[]):

    discovered.append(v)    
    for w in graph[v]: # for the graph of adjacent matrix
        if w not in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered # will return the nodes searched in order


def iterative_dfs(start_v):
    
    discovered = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    return discovered

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

discovered = recursive_dfs(1, [])
print(discovered)
# >>> [1, 2, 5, 6, 7, 3, 4]

discovered = iterative_dfs(1)
print(discovered)
# >>> [1, 4, 3, 5, 7, 6, 2]

"""
Difference comes out due to ...
    graph[v]: [w1, w2, w3]
    ...
Recursive: w1 > w2 > w3 orders, while
iterative: w3 > w2 > w1 orders
"""