We study the graph signal denoising problem by estimating a piecewise constant signal over an undirected graph. We propose a new Bayesian approach that first converts a general graph to a chain graph via the depth first search algorithm and then imposes a heavy-tailed t-shrinkage prior on the differences between consecutive signals over the induced chain graph. We show that the posterior computation can be conveniently conducted by fully exploring the conjugacy structure in the model. We also derive the posterior contraction rate for the proposed estimator and show that this rate is optimal up to a logarithmic factor, besides automatically adapting to the unknown edge sparsity level of the graph. We demonstrate the excellent empirical performance of the proposed method via extensive simulation studies and applications to stock market data.MSC Codes 62F15