Depth-first search on a directed graph

Описание: Depth-first search algorithm 👇

What is a depth-first search (DFS) algorithm?
The Depth-first search algorithm is a graph traversal algorithm. It might be used to find a path, but it cannot be used to find the shortest one. The algorithm is implemented in a recursive manner, where it:
a) explores all paths leading from one adjected node.
b) once visiting the last reachable node, it backtracks to the previous node.
c) explore the next adjected node.
It has a time complexity of (V+E) and memory complexity of O(V)*

DFS is the backbone of many algorithms, and augmented allows for finding strongly connected components, checking if the graph is connected, and defining articulation points and bridges.


What is the visit function?
The visit function represents the operation we want to perform on the graph's nodes.
It might be a function that, for example:
a) compares the node with a target
b) store nodes in some order
c) modify it (as in the video, where the color of the given vertex is changed)

Pros:
a) It's easy to implement.
b) It might be faster than a breadth-first search when there are multiple paths to the target node/s.

Cons:
a) It cannot be used to find the shortest path.
b) It might consume more memory than a breadth-first search. In the worst case, the stack call might store V frames* (Imagine a graph that looks like a linked list).


Best,
Albert 🤘

*Where V represents the number of vertexes, and E the number of edges in the graph.


#depthfirstsearch #dfs #algorithm #coding #programming #computerscience #python #python3