# Title: Depth-first search
# Heading: Python Program for Depth-First Search (DFS)
# Level: intermediate
# Tags: dfs, depth-first search, graph traversal, recursion
# Time: O(V + E)
# Space: O(V)
# About: Visits the nodes of a graph from a start node, following each path as deep as it goes before backing up to try the next.

def dfs(graph, start):
    """Every node reachable from start, in depth-first order."""
    order = []
    seen = set()

    def visit(node):
        seen.add(node)
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                visit(neighbour)  # go deeper before the next one

    visit(start)
    return order


# Each node, and the nodes it's joined to by an edge
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
print("DFS from A:", dfs(graph, "A"))