Depth-first search (DFS), is an algorithm for tree traversal on graph or tree data structures. It can be implemented easily using recursion and data structures like dictionaries and sets.
Consider this graph, implemented in the code below:
# Using a Python dictionary to act as an adjacency list graph = { 'A' : ['B','C'], 'B' : ['D', 'E'], 'C' : ['F'], 'D' : [], 'E' : ['F'], 'F' : [] } visited = set() # Set to keep track of visited nodes. def dfs(visited, graph, node): if node not in visited: print (node) visited.add(node) for neighbour in graph[node]: dfs(visited, graph, neighbour) # Driver Code dfs(visited, graph, 'A')
visited
is a set that is used to keep track of visited nodes.dfs
function is called and is passed the visited
set, the graph
in the form of a dictionary, and A
, which is the starting node.dfs
follows the algorithm described above:
visited
set.dfs
function is invoked again.Since all the nodes and vertices are visited, the average time complexity for DFS on a graph is , where is the number of vertices and is the number of edges. In case of DFS on a tree, the time complexity is , where is the number of nodes.
Note: We say average time complexity because a set’s
in
operation has an average time complexity of . If we used a list, the complexity would be higher.
RELATED TAGS
View all Courses