# Implement a depth-first search algorithm and breadth-first search algorithm, use an undirected graph, and develop a recursive algorithm for searching for all the vertices of a graph or a tree data structure.

What is Depth-first search?
• Depth-first search is a recursive algorithm used to traverse tree or graph data structure.
• It is called depth-first search because it starts with root node and follows each path to its greatest depth before moving to next path.
• It uses stack data structure i.e. LIFO(Last In First Out).
• Time Complexity is O(V+E)
•   where, V = Vertices,
E = Edges
``````#graph is a dictionary data structure, each vertex consist of
graph={'A':['b','c'],
'B':['d','e'],
'C':['f'],
'D':[],
'E':['f'],
'F':[]}

#visited is a set which keeps track of visited node,
#initially it is empty
visited = set()

def dfs(visited, graph, node):
#checks if node is present in visited or not
if node not in visited:
#if not present then print it and add in visited
print(node)

for neighbor in graph[node]:
dfs(visited, graph, neighbor)
#for each neighbour of current node,
#dfs function is invoked
dfs(visited, graph, 'A')`````` ``````graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}

visited = []		 # List to keep track of visited nodes.
queue = []     		#Initialize a queue

def bfs(visited, graph, node):
visited.append(node)
queue.append(node)

while queue:
s = queue.pop(0)
print (s, end = " ")

for neighbour in graph[s]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)

bfs(visited, graph, 'A')

``````