To accomplish reliable and efficient information routing, strong paths connecting all nodes are required in vehicular ad hoc networks (VANETs). Classical algorithms in graphic theory could find only one minimum spanning tree (MST) in VANETs. Swarm intelligence paradigms are able to obtain several alternatives to MST, which is useful for improving reliability of VANETs. This paper proposes a binary coded artificial bee colony (BABC) algorithm for tackling the spanning tree construction problem. A two-element variation technique is designed to keep the consistence of binary coded solutions. The proposed algorithm is applied to tackle a roadside-to-vehicle communication example. The success rate and average hitting time of the algorithm to find MST are also analyzed. It is found that the BABC algorithm could find MST with 92% probability. Though it is slower than Kruskal algorithm in terms of computational time, the BABC algorithm can attain several suboptimal spanning trees in one run. This suggests that the algorithm would be useful under the condition that tree paths are required to be rebuilt frequently while the network topology is unchanged in a short period.