Дослідження та реалізація паралельного алгоритму пошуку в глибину для багатоядерних систем

Abstract

У роботі розглянуто реалізацію та аналіз паралельного алгоритму пошуку в глибину (Depth-First Search,

This paper presents the implementation and analysis of a parallel Depth-First Search (DFS) algorithm for processing graph structures. The features of the classical sequential DFS are analyzed, and the main challenges of its parallelization in a multithreaded environment are identified. The adjacency list is justified as the primary data structure for graph representation.A parallel DFS algorithm is implemented in Python using the threading library. A parallelization model based on distributing graph subtrees among threads with synchronized access to shared data structures is proposed. Experimental evaluation is conducted on graphs of various sizes and different numbers of threads.The results show that the parallel DFS algorithm has limited scalability due to the inherently sequential nature of DFS and synchronization overhead. Nevertheless, the proposed approach can be applied to analyze the performance of parallel graph traversal algorithms in multithreaded software systems.