DFS Iterating

dfs_iterative.py

# graph is represented by adjacency list: List[List[int]]
# s: start vertex
def dfs_iterating(graph, s):
    # set is used to mark visited vertices
    visited = set()

    # create a stack for DFS
    stack = []

    # Push vertex s to the stack
    stack.append(s)

    while stack:
        current_vertex = stack.pop()

        # Stack may contain same vertex twice. So
        # we need to print the popped item only
        # if it is not visited.
        if current_vertex not in visited:
            print(current_vertex)
            visited.add(current_vertex)

        # Get all adjacent vertices of current_vertex
        # If an adjacent has not been visited, then push it to stack
        for v in graph[current_vertex]:
            if v not in visited:
                stack.append(v)