Depth-first search (DFS) is a technique to traverse a graph.

**1)**For an unweighted graph, we can produce the minimum spanning tree using DFS traversal of the graph.

**2) Detecting cycle in a graph**

A graph has cycle if and only if we see a
back edge during DFS. So we can run DFS for the graph and check for back edges.

**3) Path Finding**

We can use it to find the path between two
vertices of graph.

**4) To test if a graph is bipartite**

We can augment either BFS or DFS when we
first discover a new vertex, color it opposite its parents, and for each other
edge, check it doesn’t link two vertices of the same color. The first vertex in
any connected component can be red or black!

**5)**Finding Strongly Connected Components of a graph a directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex.

**6)**Solving puzzles with only one solution, such as mazes.

## No comments:

## Post a Comment