4
Depth First Search (DFS) Algorithm
source link: https://dev.to/ayabouchiha/depth-first-search-dfs-algorithm-3gjp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Hi, today, we're going to talk about Depth First Search (DFS)
Definition of Depth First Search
- Depth First Search: is an algorithm for traversing or searching in tree or graph data structure using recursion and Stack data structure.
Time & Space complexity of Depth First Search (DFS)
Space complexlity
O(V)
Time complexity
O(V+E)
Depth First Search applications
- Counting connected components
- Solving Sudoku Puzzles
- Topological sorting
- Pathfinding
- Finding Strongly Connected Components of a graph
Depth First Search implementation in Python
# code from https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
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)
dfs(visited, graph, 'A')
Enter fullscreen modeExit fullscreen mode
#day_28
References & useful Resources
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK