Реалізація паралельного алгоритму пошуку Depth-First Search

Abstract

An optimized parallel Depth-First Search algorithm for graphs has been developed. A detailed analysis of existing DFS methods was conducted, and the choice of tools for parallel execution and modeling of time delays between graph nodes was justified. The advantages and disadvantages of classical approaches were identified, and methods for their optimization were proposed. The use of the ThreadPoolExecutor library in Python was suggested for implementing multithreaded computation. Special attention was given to thread efficiency, load balancing, and minimizing synchronization overhead. A software implementation of the parallel Depth-First Search algorithm was created, significantly reducing execution time, especially for large graphs. Testing confirmed a reduction in execution time by 1.5-2 times compared to the sequential version, demonstrating the effectiveness of the multithreading approach. The obtained results can be applied to real-time tasks, social network analysis, route optimization, and distributed computing systems.