from collections import deque # Pythons queue implementation

def dfsRecursive(graph, start, visited=[]):
	# Write your code here
	return visited
	
def dfsIterative(graph, start):
	stack = []
	visited = []
	stack.append(start)
	# Write your code here
	# stack.pop() will return and remove the element added last
	return visited
	
def bfs(graph, start):
	queue = deque()
	visited = [start]
	queue.append(start)
	# Write your code here
	# queue.popleft() will return and remove the element added first
	# queue.append(elem) will append elem to queue
	return visited
	

# Here is a simple graph to test on
# What does it look like?
graph = {'a': ['b', 'd'],
         'b': ['c'],
		 'c': [],
		 'd': ['c']}
		 
print(dfsRecursive(graph, 'a'))
print(dfsIterative(graph, 'a'))
print(bfs(graph, 'a'))


# Here is a more complex graph
# When your code is working on the simple graph, try it on this
#graph = {'a': ['b', 'f', 'h', 'g'], 
#         'b': ['a', 'c'], 
#		 'c': ['b', 'd', 'f'], 
#		 'd': ['c', 'e', 'g'], 
#		 'e': ['d'], 
#		 'f': ['a', 'c'], 
#		 'g': ['a', 'd'], 
#		 'h': ['a']}

def isAcylic(graph):
	# Modify this to return true if a graph is acyclic and false otherwise
	# How might you use a search for this?
	return False