Analysis of the Depth First Search Algorithms

Abstract

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.