Data Structure & Algorithm in Java

⌘K
  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Graphs
  5. Graph Traversals-DFS & BFS

Graph Traversals-DFS & BFS

  • Depth-First Search (DFS)
  • Breadth-First Search (BFS).

Depth-first search (DFS)

DFS works by starting at the root node of a graph and exploring all of the nodes in the left subgraph of the root node before moving on to the right subgraph. This process is then repeated for each of the child nodes of the root node, and so on.

DFS is a good algorithm for finding all of the paths between two nodes in a graph, or for finding all of the nodes in a graph that are reachable from a given node. It is also a good algorithm for finding the topological order of a directed acyclic graph (DAG).

Breadth-first search (BFS)

  1. Select a starting vertex and enqueue it into a queue. Mark the starting vertex as visited.
  1. While the queue is not empty, repeat the following steps:
  1. Continue until the queue is empty, indicating that all reachable vertices have been visited.

image 62
image 63
image 64

Applications of BFS and DFS

BFS and DFS are both powerful algorithms with a variety of applications

Here are a few examples:

BFS:

  • Finding the shortest path between two nodes in a graph
  • Finding all of the nodes in a graph that are within a certain distance of the root node
  • Finding the minimum spanning tree of a graph
  • Testing for bipartiteness in a graph

DFS:

  • Finding all of the paths between two nodes in a graph
  • Finding all of the nodes in a graph that are reachable from a given node
  • Finding the topological order of a directed acyclic graph (DAG)
  • Detecting cycles in a graph
  • Finding strongly connected components in a graph

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *