DFS explores as far as possible along each branch, then backtracks. Implement it with a stack or with recursion. BFS (CS course) uses a queue and finds hop-shortest paths. DFS does not.

Goal

DFS a Kenya graph from Nairobi and print the visit order.

Recursive DFS

graph = {
    "Nairobi": ["Nakuru", "Mombasa"],
    "Mombasa": ["Nairobi", "Kisumu"],
    "Kisumu": ["Mombasa", "Nakuru"],
    "Nakuru": ["Nairobi", "Kisumu", "Eldoret"],
    "Eldoret": ["Nakuru"],
}

def dfs(graph, start):
    seen = set()
    order = []

    def visit(node):
        if node in seen:
            return
        seen.add(node)
        order.append(node)
        for nbr in graph[node]:
            visit(nbr)

    visit(start)
    return order

print(dfs(graph, "Nairobi"))

Stack DFS (same idea)

graph = {
    "Nairobi": ["Nakuru", "Mombasa"],
    "Nakuru": ["Nairobi", "Eldoret"],
    "Mombasa": ["Nairobi"],
    "Eldoret": ["Nakuru"],
}

def dfs_stack(graph, start):
    seen = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for nbr in reversed(graph[node]):
            if nbr not in seen:
                seen.add(nbr)
                stack.append(nbr)
    return order

print(dfs_stack(graph, "Nairobi"))

Neighbour order changes the walk. Mark seen when you first discover a node so cycles do not loop forever.

Tip

DFS is the engine under topological sort and “are these two cities in the same connected piece?”. Shortest hops still want BFS. Weighted kilometres want Dijkstra.