Category: C/C++

BFS (Breadth-First Search) and DFS (Depth-First Search)

Some essential definitions:

typedef char Element;

struct Node 
{
  Node( Element inputData ) : data( inputData ) { 
    cout << "Construct " << data << endl; 
  }
  
  ~Node() { 
    cout << "Destruct " << data << endl;
    
    if( lchild != NULL ) {
      delete lchild;
      lchild = NULL;
    }
    
    if( rchild != NULL ) {
      delete rchild;
      rchild = NULL;
    }
  }

  Element data;
  Node *lchild;
  Node *rchild;
};

typedef Node* Tree;

BFS: Breadth-First Search

// BFS
void breadthFirstSearch(Tree root)
{
  queue<Node *> nodeQueue;
  nodeQueue.push (root);
  Node *node;
  while (!nodeQueue.empty()) {
   node = nodeQueue.front();
   nodeQueue.pop ();
   cout << node->data;

   if (node->lchild) {
     nodeQueue.push(node->lchild);
   }

   if (node->rchild) {
     nodeQueue.push(node->rchild);
   }
  }
}

DFS: Depth-First Search

// DFS (iterative)
void depthFirstSearch(Tree root)
{
  stack<Node *> nodeStack;
  nodeStack.push (root);
  Node *node;
  while (!nodeStack.empty ()) {
   node = nodeStack.top();
   nodeStack.pop ();
   cout << node->data;

   if (node->rchild) {
     nodeStack.push(node->rchild);
   }

   if (node->lchild) {
     nodeStack.push(node->lchild);
   }
  }
}

// DFS (recursive)
void depthFirstSearchRecursive(Tree root)
{
  if (root) {
    cout << root->data;

    if (root->lchild) {
     depthFirstSearchRecursive(root->lchild);
    }

    if (root->rchild) {
     depthFirstSearchRecursive(root->rchild);
    }
  }
}

Test

Define a class TreeBuilder to build a tree and destroy it.

class TreeBuilder
{
public:
  TreeBuilder( Element data[] ) : index_( 0 ) {
   constructTree( root_, data );  
  }

  ~TreeBuilder() {
   destructTree( root_ );
  }

  Tree tree() const { return root_ ;}
 
private:
  void constructTree(Tree &root, Element data[])
  {
    Element e = data[index_++];
    if (e == '#') {
     root = NULL;
    }
    else {
     root = new Node (e);
     constructTree(root->lchild, data);
     constructTree(root->rchild, data);
    }
  }

  void destructTree(Tree root) {
    if( root != NULL ) {
      delete root;
      root = NULL;
    }
  }

private:
  int index_;
  Tree root_;
};

Test BFS and DFS.

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

...

int main(int argc, char** argv) 
{
  Element data[15] = { 'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#' };	
  
  TreeBuilder builder( data );
  
  auto tree = builder.tree();

  cout << endl;

  cout << "BFS result：";
  breadthFirstSearch(tree);

  cout << endl;
  
  cout << "DFS (iterative) result：";
  depthFirstSearch(tree);

  cout << endl;

  cout << "DFS (recursive) result：";
  depthFirstSearchRecursive(tree);

  cout << endl;
  
  return 0;
}

Build and run it.

g++ main.cpp --std=c++14
./a.out
Construct A
Construct B
Construct D
Construct E
Construct C
Construct F
Construct G

BFS result：ABCDEFG
DFS (iterative) result：ABDECFG
DFS (recursive) result：ABDECFG
Destruct A
Destruct B
Destruct D
Destruct E
Destruct C
Destruct F
Destruct G

Use valgrind to check if there is any memory leak.

valgrind --leak-check=yes ./a.out
...
==30852== HEAP SUMMARY:
==30852==     in use at exit: 0 bytes in 0 blocks
==30852==   total heap usage: 12 allocs, 12 frees, 74,024 bytes allocated
==30852== 
==30852== All heap blocks were freed -- no leaks are possible
==30852== 
==30852== For counts of detected and suppressed errors, rerun with: -v
==30852== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Use gdb to find where to throw a C++ exception

Here is a simple example about how to find where to throw a C++ exception.

#include <iostream>
#include <stdexcept>

using namespace std;

void computeIntegral() {
  throw std::runtime_error( "Input data is not valid" );  
}

int main(int argc, char** argv) {
  try {
    computeIntegral();
  } catch( std::runtime_error &e ) {
    cout << "Caught an exception: " << e.what() << endl;
  }
  
  return 0;
}

Build and run it.

g++ testException.cpp --std=c++14
./a.out
Caught an exception: Input data is not valid

Now use gdb to debug it.

gdb --args ./a.out
(gdb) catch throw
Catchpoint 1 (throw)
(gdb) r
...
(gdb) bt
#0  __cxxabiv1::__cxa_throw (obj=0x614ca0, 
    tinfo=0x6020c0 <_ZTISt13runtime_error@@GLIBCXX_3.4>, 
    dest=0x400a40 <_ZNSt13runtime_errorD1Ev@plt>)
    at ../../../../gcc-8.3.0/libstdc++-v3/libsupc++/eh_throw.cc:80
#1  0x0000000000400bd5 in computeIntegral() ()
#2  0x0000000000400c00 in main ()

Achieve polymorphism using pointer or reference

It is very common to use pointer to achieve polymorphism. For example,

#include <iostream>
 
using namespace std;

// Base class
class A {
public:
  virtual void output() = 0;
};

// Derived class B
class B : public A {
public:
  void output() override {
    cout << "From derived class B" << endl;
  }
};

// Derived class C
class C : public A {
public:
  void output() override {
    cout << "From derived class C" << endl;
  }
};

// Client code
int main(int argc, char** argv) 
{
  A *b = new B;
  A *c = new C;
  
  int flag = 0;
  cin >> flag;
  
  auto t = flag == 0 ? b : c;
  t->output();
  
  delete b;
  delete c;
  
  return 0;
}

Build the above code, and test it.

g++ -o testrefer main.cpp  --std=c++14

./testrefer
0
From the derived class B

./testrefer
1
From the derived class C

What if there are two objects of derived classes instead of two pointers of them in the client code? The answer is using reference.

// Client code
int main(int argc, char** argv) 
{
  B b;
  C c;
 
  int flag = 0;
  cin >> flag;
  
  auto& t = flag == 0 ? static_cast< A& >( b ) : static_cast< A& >( c );
  
  t.output();
  
  return 0;
}

Build and test it, and get the same output.

g++ -o testrefer main.cpp  --std=c++14

./testrefer
0
From the derived class B

./testrefer
1
From the derived class C

What if the derived class in CRTP is a template class?

CRTP (Curiously Recurring Template Pattern) is a very useful skill to achieve static polymorphism.

How to achieve CRTP if the derived class is a template class? Here is an example.

#include <iostream>
#include <string>

using namespace std;

// Base class A
template< typename Type, template< typename > class Derived >
class A {
  public:
    A() = default;
    virtual ~A() = default;
    
    void output( Type num ) {
      cout << "From base A, ";
      static_cast< Derived< Type > * > (this)->speak( num );
    }
    
  protected:
    virtual void speak( Type num ) = 0;
};

// Derived class B, override the protected method speak()
template< typename Type >
class B : public A< Type, B > {
  friend class A< Type, B >;
  public:
    using A< Type, B >::A;
    
  protected:
    void speak( Type num ) override {
      cout << "I am B, and I got " << std::to_string( num ) << endl;
    }      
};

// Derived class C, override the protected method speak()
template< typename Type >
class C : public A< Type, C > {
  friend class A< Type, C >;
  public:
    using A< Type, C >::A;
    
  protected:
    void speak( Type num ) override {
      cout << "I am C, and I got " << std::to_string( num ) << endl;
    }   
};

// Client code
int main(int argc, char** argv) {
  B< float > b;
  b.output( 5 );
  
  C< float > c;
  c.output( 8 );

  return 0;
}

Use g++ to compile the above code, and get the outputs.

g++ -o crtptest main.cpp --std=c++14
./crtptest
From base A, I am B, and I got 5.000000
From base A, I am C, and I got 8.000000