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
#list of adjacent node stored.
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)
visited.add(node)
for neighbor in graph[node]:
dfs(visited, graph, neighbor)
#for each neighbour of current node,
#dfs function is invoked
dfs(visited, graph, 'A')
Breadth First Search
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')