C++

DFS Time Complexity

DFS stands for Depth-First Search. It refers to how nodes of a tree are visited until the desired node is located. For simplicity, all the nodes in this article shall be visited. The idea is to see all the nodes, with each node visited once. A node is also called a vertex. Depth-first search can be in one of three orders: Pre-order, In-order, or Post-order. Pre-order traversal is used in this article. This article uses the following tree is used to illustrate Pre-order for Depth-First Search:


A branch in the tree is called an edge. This article aims to illustrate what is known as the time complexity for Depth-First Search. DFS is first briefly explained. C++ is used for code illustration.

Pre-Order Traversal for Depth-First Search

The algorithm is as follows:

1) Visit the current vertex.
2) Traverse the left sub-tree of the current vertex in a recursive manner.
3) Traverse the right sub-tree of the current vertex in a recursive manner.

For the previous tree, the first vertex to be visited is A. This is the current vertex. Recursively traversing the left sub-tree and then the right sub-tree means visit B while the visiting of C is recorded in the memory to be visited later.

At B, B is the current vertex. Recursively traversing the left sub-tree and then the right sub-tree means visit E while the visiting of F is recorded in the memory to be visited later.

At E, E is the current vertex. E has no left or right sub-tree (no edges). The last recording in memory for visiting was the right sub-tree (edge) for B. The right sub-tree for B consists of F preceded by its edge. At this point, F is visited.

The previous recording in memory for visiting now is the right sub-tree (edge) for A. The right sub-tree for A recorded consists of C followed by its edges and children. At this point, C is visited. C has three edges. According to the algorithm, the left edge is accessed first.

When the left edge is accessed, G is visited. There is no child for G. By the algorithm, H shares the same parent with G, and as it is on the right of G, it is visited next.

“I” happens to be on the right of H and shares the same parent with H. By the algorithm, any node on the right of another node has to be visited after the node was visited. It does not matter if the node just visited is on the right of another node. So “I” is visited next.

There is no node on the right of “I”. C and all its descendants have been visited. However, note that there is a node on the right of C. This node is D. By the algorithm, any node on the right of another node has to be visited after the node (visited). It does not matter if the node visited was on the right of some other node. So D is visited next.

D has two children, J and K. J is on the left of K. J is visited first before K.

Depth-First Search Algorithm can be summarized as follows: After visiting the root, visit the left vertex while recursively going down on the left. From the bottom leftmost vertex, visit the right siblings of that vertex, and then recursively go up the tree, rightward and coming down from time to time appropriately.

With that, the DFS sequence of the previous tree is: A, B, E, F, C, G, H, I, D, J, K.

Time Complexity

The previous tree has 11 vertices and 10 edges. If the tree is well-stored, then the scanning of the whole tree will involve 11 vertices and 10 edges. This is an appreciation of the speed of operation of Depth-First Search. It is time complexity. It is written as:

O(|V|+|E|)

Where |V| is the number of vertices (nodes) and |E| is the number of edges. For this tree, the total is 21 = 11 + 10. The “O” has to be there.

Structure for the Tree

The tree organization can be described as follows:

Vertex A: Children: B, C, D
Vertex B: Children: E, F
Vertex C: Children: G, H, I
Vertex D: Children: J, K
Vertex E
Vertex F
Vertex G
Vertex H
Vertex I
Vertex J
Vertex K

The previous tree will be stored in an unordered_map of vectors. A vertex is a key, and the children are the values of the key’s vector. Vertices from E to K have no children.

C++ Coding

The program can begin with the following heading:

    #include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;

 

C++ Coding for the Unordered_map-of-Vectors

The unordered_map-of-vectors is created with the following code:

    unordered_map <char, vector<char> > umv = { {'A', {'B', 'C', 'D'}},
                                                {'B', {'E', 'F'}},
                                                {'C', {'G', 'H', 'I'}},
                                                {'D', {'J', 'K'}},
                                                {'E', {}},
                                                {'F', {}},
                                                {'G', {}},
                                                {'H', {}},
                                                {'I', {}},
                                                {'J', {}},
                                                {'K', {}}};

 
This can be placed just below the previous heading.

The Depth-First Function

It is a recursive function that prints each vertex (node) visited. It is:

    void depthFirstSearch(char parent) {
            cout << parent << ' ';    //print vertex    
        for (int i=0; i<umv[parent].size(); i++) {
            depthFirstSearch(umv[parent][i]);
        }
    }

 
After printing the left vertex, the for-loop would print the right vertices. The for-loop has the recall.

C++ Main Function

A suitable main function for the program is:

    int main(int argc, char **argv)
    {
        depthFirstSearch('A');
        cout << endl;
        return 0;
    }

 
The algorithm for depth-first search is as follows:

1) Visit the current vertex.
2) Traverse the left sub-tree of the current vertex in a recursive manner.
3) Traverse the right sub-tree of the current vertex in a recursive manner.

This can be interpreted as follows: After visiting the root, visit the left vertex, recursively going down on the left. From the bottom leftmost vertex, visit the right siblings of that vertex, and recursively go up the tree, rightward, coming down from time to time, appropriately.

The time complexity for the depth-first search algorithm is:

O(|V|+|E|)

Conclusion

DFS stands for Depth-First Search. It refers to how nodes of a tree are visited until the desired node is located. For simplicity, all the nodes of the tree of this article have been visited. The idea is to visit all the nodes, with each node visited once. A node is also called a vertex. Depth-first search can be in one of three orders: Pre-order, In-order, or Post-order. In this article, Pre-order traversal has been used.

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.