Can someone explain to me in-deepth about BFS, DFS and Dijkstras algorithme?

QuestionsCategory: QuestionsCan someone explain to me in-deepth about BFS, DFS and Dijkstras algorithme?
Seb asked 5 months ago

Can someone explain to me in-deepth about BFS, DFS and Dijkstras algorithme?

1 Answers
Techtuna Staff answered 5 months ago

BFS –
Breadth first search(BFS) is a graph traversal algorithm that starts traversing the graph from root node and explores all the neighbouring nodes. Then, it selects the nearest node and explore all the unexplored nodes. The algorithm follows the same process for each of the nearest node until it finds the goal.
Algorithm

  • Step 1: SET STATUS = 1 (ready state)
    for each node in G
  • Step 2: Enqueue the starting node A
    and set its STATUS = 2
    (waiting state)
  • Step 3: Repeat Steps 4 and 5 until
    QUEUE is empty
  • Step 4: Dequeue a node N. Process it
    and set its STATUS = 3
    (processed state).
  • Step 5: Enqueue all the neighbours of
    N that are in the ready state
    (whose STATUS = 1) and set
    their STATUS = 2
    (waiting state)
    [END OF LOOP]
  • Step 6: EXIT
  • Example-
  • Starting from node A& de

Minimum Path P can be found by applying breadth first search algorithm that will begin at node A and will end at E. the algorithm uses two queues, namely QUEUE1 and QUEUE2QUEUE1 holds all the nodes that are to be processed while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.
starting from Node A.
1. Add A to QUEUE1 and NULL to QUEUE2.

  1. QUEUE1 = {A}  
  2. QUEUE2 = {NULL}  

2. Delete the Node A from QUEUE1 and insert all its neighbours. Insert Node A into QUEUE2

  1. QUEUE1 = {B, D}  
  2. QUEUE2 = {A}  

3. Delete the node B from QUEUE1 and insert all its neighbours. Insert node B into QUEUE2.

  1. QUEUE1 = {D, C, F}   
  2. QUEUE2 = {A, B}  

4. Delete the node D from QUEUE1 and insert all its neighbours. Since F is the only neighbour of it which has been inserted, we will not insert it again. Insert node D into QUEUE2.

  1. QUEUE1 = {C, F}  
  2. QUEUE2 = { A, B, D}  

5. Delete the node C from QUEUE1 and insert all its neighbours. Add node C to QUEUE2.

  1. QUEUE1 = {F, E, G}  
  2. QUEUE2 = {A, B, D, C}  

6. Remove F from QUEUE1 and add all its neighbours. Since all of its neighbours has already been added, we will not add them again. Add node F to QUEUE2.

  1. QUEUE1 = {E, G}  
  2. QUEUE2 = {A, B, D, C, F}  

7. Remove E from QUEUE1, all of E’s neighbours has already been added to QUEUE1 therefore we will not add them again. All the nodes are visited and the target node i.e. E is encountered into QUEUE2.

  1. QUEUE1 = {G}  
  2. QUEUE2 = {A, B, D, C, F,  E}

Now, backtrack from E to A, using the nodes available in QUEUE2.
The minimum path will be A → B → C → E.
This is all about BFS
DFS-
Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from the dead end towards the most recent node that is yet to be completely unexplored.
The data structure which is being used in DFS is stack. The process is similar to BFS algorithm. In DFS, the edges that leads to an unvisited node are called discovery edges while the edges that leads to an already visited node are called block edges.
Algorithm :-

  • Step 1: SET STATUS = 1 (ready state) for each node in G
  • Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
  • Step 3: Repeat Steps 4 and 5 until STACK is empty
  • Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
  • Step 5: Push on the stack all the neighbours of N that are in the ready state (whose STATUS = 1) and set their
    STATUS = 2 (waiting state)
    [END OF LOOP]
  • Step 6: EXIT

Example :-

Push H onto the stack

  1. STACK : H   

POP the top element of the stack i.e. H, print it and push all the neighbours of H onto the stack that are is ready state.

  1. Print H   
  2. STACK : A   

Pop the top element of the stack i.e. A, print it and push all the neighbours of A onto the stack that are in ready state.

  1. Print A  
  2. Stack : B, D  

Pop the top element of the stack i.e. D, print it and push all the neighbours of D onto the stack that are in ready state.

  1. Print D   
  2. Stack : B, F   

Pop the top element of the stack i.e. F, print it and push all the neighbours of F onto the stack that are in ready state.

  1. Print F  
  2. Stack : B  

Pop the top of the stack i.e. B and push all the neighbours

  1. Print B   
  2. Stack : C   

Pop the top of the stack i.e. C and push all the neighbours.

  1. Print C   
  2. Stack : E, G   

Pop the top of the stack i.e. G and push all its neighbours.

  1. Print G  
  2. Stack : E  

Pop the top of the stack i.e. E and push all its neighbours.

  1. Print E  
  2. Stack :  

Hence, the stack now becomes empty and all the nodes of the graph have been traversed.
The printing sequence of the graph will be :

  1. H → A → D → F → B → C → G → E

This is all about DFS.
Dijkstras algorithm
Algorithm for finding the shortest path from a starting node to a target node in a weighted graph is Dijkstra’s algorithm. The algorithm creates a tree of shortest paths from the starting vertex, the source, to all other points in the graph.