Finding the minimum weight connected dominating set (MCDS) in an arbitrary graph is an NP-hard problem and several heuristics and approximation methods have been proposed to solve it. Forwarding the messages along the virtual backbone induced by the connected dominating set (CDS) significantly reduces the routing overhead as well as the power consumption by reducing the routing nodes to the backbone nodes. This paper first defines the stochastic MCDS problem where the probability distribution function (PDF) of the random weight associated with the graph vertices is unknown. Then, it presents several learning automata-based algorithms (Algorithms 1–6) to solve the stochastic MCDS problem. Taking advantage of learning automata, the proposed algorithms significantly reduce the number of samples that must be taken from the graph to construct the MCDS. It is proved that by the proper choice of the learning rate, the probability of finding the MCDS is close enough to unity. The standard sampling method (SSM) is the baseline with which we compare the performance of the proposed algorithms. Experimental results show that Algorithm 6 significantly outperforms the SSM and the other proposed algorithms in terms of the sampling rate.