Depth First Search (DFS) Algorithm

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.

…


This content originally appeared on DEV Community and was authored by Aya Bouchiha

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

more details...

# 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')

#day_28

References & useful Resources


This content originally appeared on DEV Community and was authored by Aya Bouchiha


Print Share Comment Cite Upload Translate Updates
APA

Aya Bouchiha | Sciencx (2021-07-10T22:31:57+00:00) Depth First Search (DFS) Algorithm. Retrieved from https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/

MLA
" » Depth First Search (DFS) Algorithm." Aya Bouchiha | Sciencx - Saturday July 10, 2021, https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/
HARVARD
Aya Bouchiha | Sciencx Saturday July 10, 2021 » Depth First Search (DFS) Algorithm., viewed ,<https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/>
VANCOUVER
Aya Bouchiha | Sciencx - » Depth First Search (DFS) Algorithm. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/
CHICAGO
" » Depth First Search (DFS) Algorithm." Aya Bouchiha | Sciencx - Accessed . https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/
IEEE
" » Depth First Search (DFS) Algorithm." Aya Bouchiha | Sciencx [Online]. Available: https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/. [Accessed: ]
rf:citation
» Depth First Search (DFS) Algorithm | Aya Bouchiha | Sciencx | https://www.scien.cx/2021/07/10/depth-first-search-dfs-algorithm/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts