Depth First Search

What is Graph?
A graph is just a set of vertices (nodes), together with edges (connections) between some pairs of nodes. If the connections have a direction, the graph is said to be “directed graph”, otherwise the graph is said to be “undirected graph”.

A graph G = (V, E) with V, i.e. set of vertices and E, i.e. set of edges.

Searching a graph: Systematically follow the edges of a graph to visit the vertices of the graph. And is used to discover the structure of a graph.

Standard graph searching algorithms are

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

Problem Statement
Deeply search a graph to make logical tree. 
Depth First Search
Depth first is an algorithm for traversing or searching a tree. It explore edges out of the most recently discovered vertex v. When all edges of v have been explored, backtrack to explore other edges leaving the vertex from which v was discovered (its predecessor). 

 “Search as deep as possible first.”

Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree. 

Insertion sort

In insertion sort, we compares adjacent elements and swap them, if they are out of order. We take the next element and insert into the sorted list that we maintained in the beginning of the array and repeats the procedure on it and so on.

Advantages: 

Insertion sort provides several advantages

• Insertion sort takes advantage of pre-sorting
• Simple implementation
• Efficient for small data sets
• Stable: does not change the relative order of elements with equal keys
• O(1) extra space
• O(n²) comparisons and swaps
• Adaptive: O(n) time when nearly sorted
• Very low overhead
• Online: New elements can be added during the sort