Open Access Open Access  Restricted Access Subscription or Fee Access

Analysis of the Depth First Search Algorithms

Navneet Kaur, Deepak Garg


When the traditional Depth First Search(DFS) algorithm is used for searching an element in the Directed Acyclic Graphs (DAGs),then a lot of time is wasted in the back-tracking .But this paper discusses the Reverse Hierarchical Search (RHS) algorithm .For the DAG tree structure the RHS algorithm provides the better performance by avoiding the unnecessary search .This paper also presents a parallel formulation of the Depth First Search which retains the storage efficiency of the sequential depth first search and can be mapped on to any MIMD architecture. In this paper we have tried to improve the searching of any node in the DFS by combining the features of both the RHS algorithm and the parallel formulation of the DFS which helps in maintaining the storage efficiency and reduce the search which is unnecessary. In the RHS algorithm we use the previous node information (so that the duplicity can be prevented) to find the next nodes for searching. The main features that affect the parallel formulation is the dynamic work distribution technique which divides the work between different processors .The performance of the parallel formulation is strongly affected by the technique of work distribution and various features of the architecture such as presence or absence of shared memory, relative speed of the communication network. When we combine the features of both RHS algorithm and parallel formulation of DFS, it gives good performance.


RHS Algorithm, Parallel Formulation, DFS, Work Distribution Schemes, Directed Acyclic Graphs, MIMD Architecture

Full Text:



Jon Freeman, Parallel Algorithms for Depth - First Search, University of Pennsylvania,1991,Technical Report.

V.Nageshwara Rao, Vipin Kumar, Parallel Depth First Search, part1 implementation, Department Computer Sciences, University of Texas, Austin,Texas 78712

Mark E. Stickel and W. Mabry Tyson ,An Analysis of Consecutively Bounded Depth - First Search with Application in Automated deduction , Artificial Intelligence Center SRI International ,pp. 1074-1075.

Richard E. Korf , Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Department of Computer Science, Columbia University,1985.

Lopamudra Nayak, Design and Analysis of a Reverse Hierarchical Graph Search Algorithm, International Journal of Advanced Research in Computer Science, Volume 2, No. 4, July-August 2011.

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rdEdition, Cambridge, MA: MIT Press, September 2009

T.H.Lai and Sartaj Sahni. Anomalies in parallel branch and bound algorithms. In proceedings of International Conference on Parallel Processing, pages 183-190,1983.

J. Parallel algorithms for depth-first searches I. planar graphs. SIAM Journal on Computing, 15(3):814-830, August 1986.,1985 ustin R. Smith.

Vipin Kumar and V. Nageshwara Rao.Parallel depth-first search,part II: Analysis. International Journal of ParallelProgramming,16(6):501-519,December 1987.

O.Vornberger B.Monien and E.Spekenmeyer.Superlinear Speedup for Parallel Backtracking.Technical Report 30, Univ.of Paderborn,FRG,1986.

A .Gottlieb et al .The NYU ultracomputer -designing a mimd , shared memory parallel computer. I EEE Transactions on computers, 175-189,February 1983.

G. F. Pfister et al. The IBM research parallel processor prototype (rp3).In proceedings of International conference on Parallel Processing, pages 764-797,1985.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. 0070131430. McGraw-Hill Companies, 1

John F. Dillenburg and Peter C. Nelson*,Improving the Efficiency of Depth-First Search by Cycle Elimination Department of Electrical Engineering and Computer Science (M/C 154) University of Illinois Chicago, IL 60680 U.S.

Ellis Horowitz and Sartaj Sahni. Fundamentals of Computer Algorithms .Computer Science press, Rockville, Maryland,1978.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.