Graph Traversals in C++

Graph traversals in the form of Depth-First-Search (DFS) and Breadth-First-Search (BFS) are one of the most fundamental algorithms in computer science. As the use of these algorithms plays an essential role in tasks such as cycle-detecting, path-finding, and topological sorting. For that reason, it is important to know how to implement a simple generic version of these functions.

The first point to consider before implementing a graph traversal algorithm is to identify what type of graph we want to traverse. To select a graph we have to ask ourselves if we want the graph to be directed or undirected? Will the graph be disconnected? Will it support cycles? In the case of this blog post, I decided to use an undirected graph. What this means is that the traversal algorithms may need slight modifications depending on the type of graph being used; nevertheless, the fundamental structure of the algorithm will remain the same.

The undirected graph presented in this example will use an adjacency list representation. The graph is implemented using a hash map of key-value pairs between each vertex and the list of neighbor vertices around it. The implementation of the undirected graph is presented below:

Graph Implementation:

template<typename VertexType>
using UndirectedGraph = std::unordered_map<VertexType, std::vector<VertexType>>;

template<typename VertexType>
void addEdge(UndirectedGraph<VertexType>& undirected_graph, 
    const VertexType& source, const VertexType& destination)
{
    undirected_graph[source].push_back(destination);
    undirected_graph[destination].push_back(source);
}

Now that we have established an implementation for the graph, we can start thinking about the design of the traversals. In the case of graphs, the options for traversals are Depth-First-Search(DFS) and Breadth-First-Search(BFS). DFS is characterized by starting from a given vertex and then following a path until it ends, then it backtracks to the next possible path following the same procedure until the whole graph is traversed. In the case of BFS, the traversal begins at any selected vertex from where we begin to visit the neighbor vertices at the same depth level, and then move onto each level subsequently until the graph is fully traversed. A graphical visualization of both types of traversals in a tree graph is presented below:

Breadth First Search (BFS) Visualization

Depth First Search (DFS) Visualization

In regards to the implementation details of DFS and BFS, there are various commonalities shared between both algorithms. The main one being the use of a set to keep track of the visited nodes to prevent the traversal from being stuck in a cycle. The key difference between them is the use of a different data structure to process the order of each vertex. For DFS a stack is used as the Last-In-First-Out (LIFO) order serves the purpose of traversing down a path and then backtrack as the traversal reaches its end. While in BFS a queue is used as its First-In-First-Out structure helps navigate each vertex on a level by level basis. The generic implementation for both traversals is presented below:

BFS Implementation:

template<typename VertexType, typename Function = std::invoke_result<void(VertexType&)>::type>
void BFS(const UndirectedGraph<VertexType>& undirected_graph, VertexType current_vertex,
    const Function& process_vertex_function)
{
    std::queue<VertexType> queue;
    queue.push(current_vertex);

    std::unordered_set<VertexType> visited_vertices;
    visited_vertices.insert(current_vertex);

    while (!queue.empty())
    {
        current_vertex = queue.front();
        queue.pop();

        process_vertex_function(current_vertex);
        
        for (auto neighbor_vertex : undirected_graph.at(current_vertex))
        {
            if (!visited_vertices.count(neighbor_vertex))
            {
                visited_vertices.insert(neighbor_vertex);
                queue.push(neighbor_vertex);
            }
        }
    }
}

DFS Implementation:

template<typename VertexType, typename Function = std::invoke_result<void(VertexType&)>::type>
void DFS(const UndirectedGraph<VertexType>& undirected_graph, VertexType current_vertex, 
    const Function& process_vertex_function)
{
    std::stack<VertexType> stack;
    stack.push(current_vertex);

    std::unordered_set<VertexType> visited_vertices;

    while (!stack.empty())
    {
        current_vertex = stack.top();
        stack.pop();

        if (visited_vertices.count(current_vertex))
        {
            continue;
        }

        visited_vertices.insert(current_vertex);

        process_vertex_function(current_vertex);

        for (auto neighbor_vertex : undirected_graph.at(current_vertex))
        {
            stack.push(neighbor_vertex);
        }
    }
}

Usage Example:

int main()
{
    UndirectedGraph<int> graph;

    addEdge(graph, 1, 2);
    addEdge(graph, 2, 6);
    addEdge(graph, 1, 3);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 5);
    addEdge(graph, 5, 7);
    addEdge(graph, 6, 7);
    
    auto print_vertex = [](auto& vertex) 
    { std::cout << vertex << ' '; };

    std::cout << "BFS: ";
    BFS(graph, 1, print_vertex);

    std::cout << '\n';

    std::cout << "DFS: ";
    DFS(graph, 1, print_vertex);
}

Graph Used in Example

Output:
BFS: 1 2 3 6 5 7 4
DFS: 1 3 5 7 6 2 4

Conclusion

Breadth-First-Search and Depth-First-Search traversals have a wide range of applications in many algorithms, thus it is essential to understand their theory and implementations. While there are various kinds of graphs with unique properties, the general structure of DFS and BFS remains very similar. Lastly, if you are interested in additional graph algorithms and more robust implementations make sure to take a look at The Boost Graph Library.

Source Code

How to Generate Permutations of a String in C++

Generating all possible permutations of a set of elements is generally done by using recursive methods. Therefore, to generate the permutations of a string we are going to use backtracking as a way to incrementally build a permutation and stop as soon as we have used every possible character in the string. The method implemented below uses this idea to solve the permutation problem:

Backtracking Method #1 (Using std::swap)

void add_permutation1(std::vector<std::string>& permutations, std::string& str, std::size_t curr_index)
{
    if (curr_index == str.size() - 1)
    {
        permutations.push_back(str);
        return;
    }

    for (auto j = curr_index; j < str.size(); ++j)
    {
        std::swap(str[curr_index], str[j]);

        add_permutation1(permutations, str, curr_index + 1);

        //Restoring string to its original state
        std::swap(str[curr_index], str[j]);
    }
}

std::vector<std::string> get_permutations1(const std::string& str)
{
    std::vector<std::string> permutations;
    
    auto str_cpy = str;
  
    add_permutation1(permutations, str_cpy, 0);

    return permutations;
}

The next backtracking method uses a similar concept with the difference of using a reduced subset with the leftover characters instead of keeping track of the current index is presented below:

Backtracking Methods #2 (Using std::rotate)

void add_permutation2(std::vector<std::string>& permutations, std::string str, 
    const std::string curr_permutation& = "")
{
    if (str.empty())
    {
        permutations.push_back(curr_permutation);
        return;
    }

    for (auto c : str)
    {
        add_permutation2(permutations, str.substr(1), curr_permutation + str[0]);

        //Rotating string one index to the left
        std::rotate(str.begin(), str.begin() + 1, str.end());
    }
}

std::vector<std::string> get_permutations2(const std::string& str)
{
    std::vector<std::string> permutations;

    add_permutation2(permutations, str);

    return permutations;
}

Fortunately, it’s not necessary to deal with any of the details of the recursive code as the C++ STL provides the function std::next_permutation that transforms the range of elements to its next permutation based on lexicographical order.

STL Method (using std::next_permutation)

std::vector<std::string> get_permutations3(const std::string& str)
{
    std::vector<std::string> permutations;

    auto str_cpy = str;

    do{
        permutations.push_back(str_cpy);
    } while (std::next_permutation(str_cpy.begin(), str_cpy.end()));
    //Stops as soon as the new permutation is lexicographically smaller than the old one (comes back to original state)
  
    return permutations;
}

Conclusion

Backtracking offers a simple and effective way of generating all possible permutations of a string. If you don’t want to deal with the implementation details of generating permutations then its possible to use functions such as std::next_permutation or std::prev_permutation to get the job done.

Source Code

How to Binary Search in C++

Binary Search is a very useful algorithm whenever we are dealing with an already sorted group of elements. If we take a look at the C++ STL we find a function called std::binary_search that implements this algorithm but upon further research, we learn that it only tells us if the search value is present in the container, rather than returning an iterator of the value found. So how do we implement a generic binary search function that finds the location of the value that we want to search? A simple implementation based on traditional binary search would look something like this:

Implementation #1

template<typename Iter, typename Val, typename Comp = std::less<>>
Iter binary_search1(Iter begin, Iter end, const Val& search_val, Comp comp = {})
{
    auto original_end = end; //saving end to return when value is not found

    while (begin != end)
    {
        auto mid = begin + (end - begin) / 2;

        if (search_val == *mid) 
        {
            return mid;
        }
        else if (!comp(search_val, *mid)) //search_val > mid
        {
            begin = mid + 1;
        }
        else //search_val < mid
        {
            end = mid;
        }
    }

    return original_end;
} 

While the first implementation follows the common steps needed to perform binary search it, is not taking advantage of C++ library features that could help shorten and simplify the code. For that reason, the second implementation presented below makes use of std::lower_bound: a function from the algorithm header that returns an iterator to the first element that is greater than or equal to the search value, or an iterator to the end of the container if no value was found.

Implementation #2 (Using lower_bound)

template<typename Iter, typename Val, typename Comp = std::less<>>
Iter binary_search2(Iter begin, Iter end, const Val& search_val, Comp comp = {})
{
    auto found_itr = std::lower_bound(begin, end, search_val, comp);

    if (found_itr != end && !comp(search_val, *found_itr)) //search_val >= found_itr
    {
        return found_itr;
    }

    return end;
}

Clearly, the use of std::lower_bound makes the implementation of binary search a rather straightforward task as it takes away from most of the error-prone details that are present in the algorithm.

Conclusion

Since C++ doesn’t provide a proper binary search function that returns the iterator of the value to be found, it is needed to write additional code to provide a generic and useful solution. Luckily, the use of std::lower_bound eases the implementation of the algorithm and allows us to enjoy the benefits of working with a sorted container.

Source Code

How to Find the Kth Largest Element in an Array

The most obvious way to find the Kth largest element in an array would be to sort the array in descending order and then access its element at the index k - 1. However, the shortcoming of this approach comes from the fact that it doesn’t solve this problem in the most optimal way with regards to time complexity.

Brute-Force Solution (Time Complexity: O(nlogn), Space Complexity: O(1))

int Kth_largest(const std::vector<int>& array, int k)
{
   std::sort(array.rbegin(), array.rend());
  
   return array[k - 1];
}

To advance towards a more optimal solution we need to make use of another data structure that provides us with better time complexity guarantees. A priority queue is an excellent tool for this kind of improvement as it allows us to compare at most K elements instead of the whole array whenever we are sorting as we traverse through the array.

Min-Heap Priority Queue Solution (Time Complexity: O(nlogk), Space Complexity: O(k))

int Kth_largest(const std::vector<int>& array, int k)
{
   std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
  
   for(auto val : array)
   {
      queue.push(val);
     
      if(queue.size() > k)
      {
          queue.pop();
      }
   }
  
    return queue.top();
}

This solution is a little more verbose than the first one, but it is still very simple and useful when time efficiency is of concern. Moreover, the previous implementation is also adaptable to the Kth smallest element problem by replacing the min-heap queue with a max-heap queue. Fortunately, the C++ STL provides an in-built function called nth_element that is implemented with partial sorting using introspective selection to offer an excellent linear average time complexity with the only downside of the rare case of a bad partition that leads to a worst possible time complexity of O(nlogn).

Nth Element Solution (Avg Time Complexity: O(n), Worst Time Complexity: O(nlogn), Space Complexity: O(1))

int Kth_largest(const std::vector<int>& array, int k)
{
   std::nth_element(array.begin(), array.begin() + k - 1, array.end(), std::greater<int>());
  
   return array[k - 1];
}

Conclusion

It is necessary to divert from the standard sorting of an array to find an optimal time efficient solution to the Kth largest element problem. Priority queues and more specialized partial sorting algorithms provide an excellent alternative to solving this issue.

Source Code

How to Iteratively Traverse a Binary Tree

Binary tree traversals are generally done in a recursive manner because this type of problem tends to be simplified by such methods. Nevertheless, the key advantage gained by using an iterative approach is the fact that the traversal will not run out of stack space. Moreover, there is always something to learn when solving a problem in an alternative way.

Below are the iterative implementations of the different types of traversals that can be done with a binary tree alongside an explanation of how they work:

Pre-Order Traversal

void print_pre_order(TreeNode* root)
{
    if (!root)
    {
        return;
    }
        
    std::stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.empty())
    {
        auto* node = stack.top();
        stack.pop();

        std::cout << node->val << ' ';

        if (node->right)
        {
            stack.push(node->right);
        }    
        if (node->left)
        {
            stack.push(node->left);
        }    
    }
}

Pre-Order traversal consists of traversing the left subtree before advancing to the right subtree. This behavior is achieved through the use of a Last In First Out (LIFO) data structure like a stack. The insertion of the right nodes occurs before the left nodes in order to make sure that the left nodes will be the first ones to be accessed.

Post-Order Traversal

void print_post_order(TreeNode* root)
{
    if (!root)
    {
        return
    }
       
    std::stack<TreeNode*> stack, out_stack;
    stack.push(root);

    while (!stack.empty())
    {
        auto* node = stack.top();
        stack.pop();

        out_stack.push(node);

        if (node->left)
        {
            stack.push(node->left);
        }
        if (node->right)
        {
            stack.push(node->right);
        }
    }

    while (!out_stack.empty())
    {
        auto* node = out_stack.top();
        out_stack.pop();

        std::cout << node->val << ' ';
    }
}

The Post-Order iterative tree traversal algorithm is slightly more complex than the Pre-Order one because the solution uses two stacks. The first stack gets the reverse Post-Order traversal in a similar manner to the algorithm used for the Pre-Order traversal with the only difference that the left node is inserted before the right one. The purpose of the second stack is to get the reverse of the first stack and in turn get the proper Post-Order traversal.

In-Order Traversal

void print_in_order(TreeNode* root)
{
    std::stack<TreeNode*> stack;
    auto* curr = root;

    while (!stack.empty() || curr)
    {
        if (curr)
        {
            stack.push(curr);
            curr = curr->left;
        }
        else
        {
            curr = stack.top();
            stack.pop();

            std::cout << curr->val << ' ';

            curr = curr->right;
        }
    }
}

In-Order traversal involves a current pointer pivot that will traverse the leftmost part of the tree and insert itself to a stack until it reaches a null value. If the current pointer is null and the stack is not empty then the pivot pointer moves towards the rightward node from the node at the top of the stack, otherwise, the traversal stops as the whole tree has been accessed.

Level-Order Traversal

void print_level_order(TreeNode* root)
{
    if (!root)
    {
        return;
    }
        
    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty())
    {
        const auto LEVEL_SIZE = queue.size();

        for (std::size_t i = 0; i < LEVEL_SIZE; ++i)
        {
            auto* node = queue.front();
            queue.pop();

            std::cout << node->val << ' ';

            if (node->left)
            {
                queue.push(node->left);
            }
            if (node->right)
            {
                queue.push(node->right);
            }
        }
    }
}

The Level-Order traversal algorithm is different from all the previous methods mentioned in the fact that it uses a First In First Out (FIFO) data structure in the form of a queue. The way it works consists of accessing every node in a single level and then insert the left and right child nodes to use them in the next cycle of iteration for each upcoming level. As a side note, it is not necessary to include the for loop to iterate through every level of the tree as the queue itself will handle this behavior; nevertheless, this is added to make a distinction for every level of the tree that is being accessed.

Conclusion

Undoubtedly, the iterative approach of traversing a binary tree traversal is a more verbose and complex solution when compared to its recursive counterpart. Despite that, implementing another way of traversing a tree adds a level of comprehension for key data structures such as stacks and queues, as well as, include the benefit of not having to worry about running out of stack space.

Source Code