Depth-first search (iterative)

"""
You'll see that the iterative version prints out 1-3-2-5-4, while the recursive version prints out 1-2-4-5-3.
What determines the different order of the handling of the nodes between the iterative and recursive versions of this code
is the fact that in the iterative version the 'for neighbor in graph' finishes adding all of the neighbors before the next
neighbor is popped off the stack, so the later neighbors get recursed before the earlier neighbors, whereas in the recursive
version the neighbors are recursed immediately as they're encountered within that for loop, so the earlier neighbors get
recursed before the later neighbors.
So, for example, if the graph says "1: [2, 3]", iterative DFS will have the 3 visited first, recursive DFS will have the 2 visited first.

Pseudocode:
dfs_i: need graph and start_node
    # create a 'visited' set and stack
    # pop from the stack while you can
    # process the vertex
    # loop through the neighbors, appending each to the stack

Interesting discussions to have / think about:
1. Why are there two checks for if a vertex is in the visited set?
 - I think the first/outer one protects you if you have a node that's pointed to by two different nodes. For example, if you have a parent pointing to two nodes, A and B, and you add both A and B to the stack, but go down B first, and then B points to A and C. You'll end up visiting C and then A, and then when you navigate back "up" the graph you'll still have another visit to A in the stack. So this check shouldn't be necessary if it's guaranteed that each node is only pointed to by one other node.
- I think the inner one just saves the program time by not adding nodes to the stack that we know have already been visited. It isn't necessary, as the outer check would catch those nodes anyway, but this way we don't have to do the .pop() operation for those nodes.
"""
def dfs_i(graph, start):
    visited = set()  # A set to keep track of visited nodes
    stack = [start]  # Initialize the stack with the start node

    while stack:
        vertex = stack.pop()  # Pop a vertex from the stack
        if vertex not in visited:
            visited.add(vertex)  # Mark the vertex as visited
            print(vertex)  # Process the vertex (e.g., print it)

            # Add neighbors of the vertex to the stack if they haven't been visited
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

graph = {
    1 : [2, 3],
    2 : [4, 5],
    3 : [],
    4 : [5],
    5 : [1],
}
dfs_i(graph, 1)  # Start DFS from vertex 1