Graph Neural Networks (GNNs) generally struggle to capture long-range dependencies and easily occur over-smoothing problem when increasing the depth of GNNs. To address these limitations, Graph Transformers (GTs) have been proposed to enlarge receptive fields and thus capture long-range dependencies. However, GTs face quadratic computational costs and rely heavily on complex positional encodings, limiting their scalability. Inspired by the widely used Mamba based on state space models (SSMs), Graph-Mamba has been introduced to deal with graph-structured data by using input-dependent node prioritization and permutation strategy. In this paper, we extend this strategy with an uncertain module by incorporating uncertainty-guided node sorting to further improve the selection of nodes for message passing. Based on this, we propose a new Uncertain-GMamba to achieve a balance between efficiency and adaptive context representation. Experimental results on multiple benchmarks demonstrate that Uncertain-GMamba surpasses many existing methods in long-range prediction tasks, achieving high accuracy with reduced computational costs.