DFS

Take a look at full implementation of DFS.

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS Operations

The primary operations that can be performed using DFS are:

• Traversal: DFS is used to traverse all nodes of a graph or tree using the concept of backtracking. It traverses by exploring a vertex then going to its adjacent vertices and further exploring them and so on, until all vertices are explored.
• Topological Sorting: DFS can be used to do Topological Sorting. Topological Sort for a graph is not possible if the graph is not a DAG (Directed Acyclic Graph).
• Detecting cycle: DFS can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree.
• Path Finding: DFS can be used to find a path between two vertices in a graph.

DFS Implementation in Python

Here is a basic implementation of DFS in Python:

```python
class Graph:

def __init__(self):  
    self.graph = defaultdict(list)  
  
def addEdge(self, u, v):  
    self.graph[u].append(v)  
  
def DFSUtil(self, v, visited):  
    visited.add(v)  
    print(v, end=' ')  
    for neighbour in self.graph[v]:  
        if neighbour not in visited:  
            self.DFSUtil(neighbour, visited)  
  
def DFS(self, v):  
    visited = set()  
    self.DFSUtil(v, visited)   \```  

DFS Exercises

Exercise #1: Path between two nodes

This exercise involves checking if a path exists between two nodes using DFS.

```python
def is_path(self, start_vertex, end_vertex):
visited = set()
self.DFSUtil(start_vertex, visited)

if end_vertex in visited:  
    return True  
return False   \```  

Exercise #2: Detect Cycle in a Graph

This exercise involves detecting a cycle in a Graph using DFS.

```python
def is_cyclic_util(self, vertex, visited, rec_stack):
visited[vertex] = True
rec_stack[vertex] = True

for neighbour in self.graph[vertex]:  
    if visited[neighbour] == False:  
        if self.is_cyclic_util(neighbour, visited, rec_stack) == True:  
            return True  
    elif rec_stack[neighbour] == True:  
        return True  
  
return False   \```  

By understanding these basic operations and exercises, you’ll have a solid foundation for working with DFS in any coding interview or real-world application.