Graph is a set of connected vertices {V} and edges {E}. A graph may be connected, disconnected, weighted or non-weighted. In other terms, Graph could also be a tree with cycles. Graph Search or Traversal can be done in two ways as explained below:

**1. Depth First Search**

In this type of search, we begin at a vertex Vi and traverse through all vertices from Vi unto Vx depth wise, until there is no adjacent vertex which is unvisited. Then we backup all the way upto an unvisited vertex Vy and continue. We continue until there are no unvisited vertices left. It represents

*in Algorithmic Problem Solving.*__Backtracking__
Depth First Search Implementation (C Language) can be found here.

**2. Breadth First Search**

In this type of search, we begin at a vertex Vi and traverse each vertex Vj that is reachable from there. Then we continue in the same way at every vertex reachable from Vj. It creates a queue of vertices visited from a given vertex and then deletes each of them if visited or after visiting them. The process is terminated once there is no non-visited vertex left. It represents

*in Algorithmic Problem Solving.*__Dynamic Programming__
Breadth First Search Implementation (C Language) can be found here.

## No comments:

Post a Comment