Graph:
In simple terms, graph is a collection of nodes and looks something like this:
There are two basic types of algos when it comes to graphs and they are:
1) Depth First Search (DFS)
2) Breadth First Search (BFS)
These algos basically define a procedure or an approach in which a path from a given source to destination,if exists,is found.
EX; Path from A to E in above fig can be A-C-E or A-B-D-E
DFS:
 |
| Right arrow is BFS and Down Arrow is DFS |
- To put in simple terms DFS goes DEEP (to children) before going on to neighbor.
- This is a simple and recursive method and often easy to implement.
- The problem with this is that the depth can be too big to actually find a feasible solution especially in case wherein our destination in the neighbor of existing nodes.
- This case needs a flag or a similar method to prevent infinite loops.
- In above figure DFS can be shown by RED DOWN arrow.
BFS:
- To put it simple terms BFS goes BROAD (to neighbors) before going on to child or deep.
- This is bit complicated compared to DFS and can be implemented iteratively using queues.
- In above figure BFS can be shown in BLACK RIGHT arrow.
Comments
Post a Comment