non recursive implementation of a dfs algorithm from future import annotations def depthfirstsearchgraph dict start str setstr explored stack setstart start while stack v stack pop explored addv differences from bfs 1 pop last element instead of first one 2 add adjacent elements to stack without exploring them for adj in reversedgraphv if adj not in explored stack appendadj return explored g a b c d b a d e c a f d b d e b f f c e g g f if name main import doctest doctest testmod printdepthfirstsearchg a depth first search on graph param graph directed graph in dictionary format param start starting vertex as a string returns the trace of the search input_g a b c d b a d e c a f d b d e b f f c e g g f output_g list a b c d e f g all x in output_g for x in list depth_first_search input_g a true all x in output_g for x in list depth_first_search input_g g true differences from bfs 1 pop last element instead of first one 2 add adjacent elements to stack without exploring them
from __future__ import annotations


def depth_first_search(graph: dict, start: str) -> set[str]:
    
    explored, stack = set(start), [start]

    while stack:
        v = stack.pop()
        explored.add(v)
        
        
        
        for adj in reversed(graph[v]):
            if adj not in explored:
                stack.append(adj)
    return explored


G = {
    "A": ["B", "C", "D"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B", "D"],
    "E": ["B", "F"],
    "F": ["C", "E", "G"],
    "G": ["F"],
}

if __name__ == "__main__":
    import doctest

    doctest.testmod()
    print(depth_first_search(G, "A"))