Tree and Graph

Tree and graph can be classified under the non linear data structure. Here I have shared few algorithms of tree and graph.

Graph algorithms

Algorithm for DFS(Depth First Search) graph traversal:

Step 1:Define a Stack of size total number of vertices in the graph.

Step 2:Select any vertex as starting point for traversal.Visit that vertex and push it on to the Stack.

Step 3:Visit any one of the adjacent vertex of the vertex which is at top of the stack which is not visited and push it on to the stack.

Step 5:When there is no new vertex to be visit then use back tracking and pop one vertex from the stack.

Step 6:Repeat steps 3, 4 and 5 until stack becomes Empty.

Step 7:When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph.

Algorithm for BFS(Breadth First Search) graph traversal:

Step 1:Define a Queue of size total number of vertices in the graph.

Step 2:Select any vertex as starting point for traversal.Visit that vertex and insert it into the Queue.

Step 3:Visit all the adjacent vertices of the vertex which is at front of the Queue which is not visited and insert them into the Queue.

Step 4:When there is no new vertex to be visit from the vertex at front of the Queue then delete that vertex from the Queue.

Step 5:Repeat step 3 and 4 until queue becomes empty.

Step 6:When queue becomes Empty, then produce final spanning tree by removing unused edges from the graph.";

Tree algorithms

Algorithm for In - order tree traversal:

Step 1:Recursively traverse left subtree.

Step 2:Visit root node.

Step 3:Recursively traverse right subtree.

Algorithm for pre - order tree traversal:

Step 1:Visit root node.

Step 2:Recursively traverse left subtree.

Step 3:Recursively traverse right subtree

Algorithm for post - order tree traversal:

Step 1:Recursively traverse left subtree.

Step 2:Recursively traverse right subtree.

Step 3−Visit root node.

Algorithm for inserting nodes in Binary Search Tree:

If root is NULL then
    create root node
    return
End If
If root exists then
    compare the data with node.data
    While until insertion position is located
        If data is greater than node.data
            goto right subtree
        else
            goto left subtree
    End While
    insert data
End If

Algorithm for searching a node in Binary Search Tree:

If root.data is equal to search.data
    return root
Else
    While data not found
        If data is greater than node.data
            goto right subtree
        Else
            goto left subtree
            If data found
                return node
    End While
    return data not found
End if

End

Algorithm for deleting a node in Binary Search Tree:

Case 1:Deleting a leaf node
    We use the following steps to delete a leaf node from BST…
   
    Step 1:Find the node to be deleted using search operation
    Step 2:Delete the node using free function (If it is a leaf)and terminate the function.
  
Case 2:Deleting a node with one child
    We use the following steps to delete a node with one child from BST…
   
    Step 1:Find the node to be deleted using search operation
    Step 2:If it has only one child, then create a link between its parent and child node.
    Step 3:Delete the node using free function and terminate the function.
   
Case 3:Deleting a node with two children
    We use the following steps to delete a node with two children from BST…
       
    Step 1:Find the node to be deleted using search operation
    Step 2:If it has two children, then find the largest node in its left subtree(OR) the smallest node in its right subtree.
    Step 3:Swap both deleting node and node which found in above step.
    Step 4:Then, check whether deleting node came to
        case 1 or case 2
        else goto step 2
    Step 5:If it comes to case 1,then delete using case 1 logic.
    Step 6:If it comes to case 2,then delete using case 2 logic.
    Step 7:Repeat the same process until node is deleted from the tree.


I hope you find this blog useful.
Please Like, comment and subscribe.