# Clone by Robert Sparks of:
# "Depth First Search" by Robert Sparks
# https://ancientbrain.com/world.php?world=2559333087
# Please leave this clone trail here.



# Clone by Robert Sparks of:
# "Pure Python (full compiler)" by Starter user
# https://ancientbrain.com/world.php?world=4251804126
# Please leave this clone trail here.



# Python code 

print ("<h1> Breadth First Search </h1>")

print ("<p style='color:green'><b> Implementing DFS in python for better understanding </b></p>") 
 

# --- Depth First Search: -----------------------------------------------------
tree = {
    'A' : ['B', 'C'],
    'B' : ['D', 'E'],
    'C' : ['F', 'G'],
    'D' : ['H', 'I'],
    'E' : [],
    'F' : [],
    'G' : [],
    'H' : [],
    'I' : []
}

visited = []
order = []

def bfs(node, visited, order):
    if (node in visited):
        return None
    queue = [node] # create queue
    visited.append(node) # starting point
    while len(queue) > 0:
        current = queue.pop(0) # nothing in visited order so start with queue
        order.append(current) # appending first visit with current node
        for neighbour in tree[current]: # iterate through the all neighbours of current node
            if neighbour not in visited: # make sure not visited before
                visited.append(neighbour)
                queue.append(neighbour)
        

bfs('A', visited, order)
print(f'What the tree looks like: {tree}')
print(f'How BFS visits the tree: {order}')

# ----------------------------------------------------------------------------