|
..........Depth First Search C++Source Code |
| by Arxwn |
|
| Tutorial Description : | This is an implementation of the depth first search! The useful thing about it , is that its all made with templates! What does that mean? Well this means that you can do DFS with any class you can come up with and it will still work! |
|
|
DFS algorithm has been around for quite some time and it is quite useful in
AI methods and especially when there is a memory or time restrictions.
This means that if there is a solution the algorithm will find it but it is likely that it won't be the best solution |
| |
| |
Class: Search Algorithm
Data Structure: Graph
Time Complexity: O(bm)
Space Complexity: O(b*m)
Optimal: no
Complete: yes
b - branching factor
m - maximum depth of graph
(from wiki) |
| |
| |
How it works: The logic behind DFS is very simple! From a selected node you go as deep as you can!
If you don't find a solution you go back a node and do the same thing! |
| |
| |
| |
In my implementation the main class is of course the node!
The node class acts as a container for your class. It has a link vector with pointers to other nodes(the links are one way). Then we have the map class and the map search class! The map class stands between the node and the map search!
Its used to measure the size of graph and to disallow duplicated nodes to be inserted.
The map search is used to find the path! If there is a path the path-exists variable is true and the path is stored in the vector!
Just make a map, add your nodes, make a map search instance and put your map in! Run the find path function and voila! |
I include a cpp file with a test program I made! |
| |
|
Download Source File ( .cpp )
|
|
| |
| |
IMPORTANT I left some debugging code in the files. It used to output the solution in txt file! If you don't want it just go to the map search class , find path function and delete all the cout and file output code! (5-6 lines top) |
| |
|
|
This tutorial was written by Arxwn.
For any problems or question please don't hesitate to post them in our forums
and i ( or anyone else who can answer them ) will reply as soon as possible
Keywords : C++ , algorithm , programming , depth first , depth first algorithm , source |
| |
| |
