Nowadays, magnetic resonance imaging (MRI) is the go-to method for safe and effective diagnosis in hospitals. However, it can be slow and costly due to repeated scans. To speed things up and reduce costs, we use a mathematical approach called compressed sensing. This method generates fewer measurements, but we need an iterative numerical method for accurate reconstruction. This research introduces an effective algorithm aimed at enhancing MRI reconstruction. The proposed algorithm employs a graph-based search approach to locate target atoms within the dictionary. Evaluated using a specifically designed cost function, the paths identified during the search are subjected to pruning techniques that strike a balance between computational complexity and reconstruction accuracy. This approach has demonstrated remarkable efficacy in MRI reconstruction. Through comparative analyses with established methods, we showcase the reconstruction capabilities of the graph search matching pursuit (GSMP) method. The results affirm that GSMP significantly enhances the accuracy of compressed MRI reconstruction.