Graph Search Algorithms

18 April 2020 - less than 1 min read time
Tags: DFS Depth graph search

Depth First Search(DFS)

---

DFS is one of the most easiest and fun graph search algorithms to learn and implement. This is because, if you are familiar with recursion, the algorithm is pretty intuitive. Let’s take a look at the pseudo code.

The main idea is to perform a depth first search on every node in the graph. If the node is new, it is marked as visited and DFS is performed on all the node’s neighbors. If the node was previously visited, then it is skipped.

Time Complexity:-

• O(V²) if the graph is implemented using an adjacency martix
• O(V + E) if the graph is implemented using an adjacency list