In wireless sensor network (WSN), data transfer from source to the destination needs an optimized network with less energy consumption. However, the optimized network with connected dominating set (CDS) of graph theory plays an important role in WSN for virtual backbone network formation. The connected dominating set is NP-hard problem with larger in size. However, the problem of the size of the network and NP-hard makes the researchers concentrate to improve the algorithms for virtual backbone. In this paper, we propose a semigraph contiguous prevalent set (SCPS) algorithm for semigraph structure to reduce NP-hard and size of the virtual backbone. The virtual back bone with SCPS algorithm applies with various protocols such as AODV, DSR, and DSDV for performance evaluation. From simulation result, we observe the network parameters such as size, diameter, average hoping and waiting time between the nodes are reduced. The proposed SCPS construction method retains the best performance ratio of $$(2 + \ln \Delta_{a} )|opt|,$$ (2+lnΔa)|opt|, whereas $$|opt|$$ |opt| is the size of any optimal adjacent dominating set (ADS) and $$\Delta_{a}$$ Δa is the maximum adjacent degree of all nodes of the network and has the low time complexity of O(n2), whereas n denotes the network size. Furthermore, the proposed SCPS virtual backbone in hardware implementation proves the network life time increases about 86% of 9 V battery of the node.