Thursday, March 6, 2008

Depth First Search without writing code

I am going to show how depth first search ( DFS ) without using any algorithm.
Actually I am making use of the algorithm which compilers already have implemented :-)
The virtual inheritance property is compiler makes sure that it follows the depth first search logic to instantiate the virtual base classes.
Here is the code and output:

/*
* =====================================================================================
*
* Filename: DepthFirstSearch.cpp
*
* Description: Without writing code DFS implementation
* A B C D
* \ / \ /
* E F
* \ /
* \ /
* G
* Version: 1.0
* Created: 03/06/2008 11:21:34 AM IST
* Revision: none
* Compiler: gcc
*
* Author: Siddhartha Singh :
* Company:
*
* =====================================================================================
*/

#include

using std::cout;
using std::endl;


class A {
public:
A() {
cout << "A()" << endl;
}
};
class B {
public:
B() {
cout << "B()" << endl;
}
};
class C {
public:
C() {
cout << "C()" << endl;
}
};
class D {
public:
D() {
cout << "D()" << endl;
}
};
class E : public virtual A, virtual public B {
public:
E() {
cout << "E()" << endl;
}
};
class F : public virtual C, virtual public D {
public:
F() {
cout << "F()" << endl;
}
};
class G : virtual public E, virtual public F {
public:
G() {
cout << "G()" << endl;
}
};

int main() try {
G g;
return 0;
} catch(...) {
cout << "Uncaught exception..." << endl;
}


--------------------------------------------------------
Output :
A()
B()
E()
C()
D()
F()
G()

So no need to write algo to find how DFS works ( Short cut to success ;-)

No comments: