With the significant attention on global climate change, regional integrated energy systems (RIES) in low-carbon city planning has become one of the most important ways for global cities to achieve the goal of energy conservation and emission reduction. However, the planning strategy used in the primary stage of RIES establishment will greatly affect the system economy and environment. In view of the lack of planning guidance mechanisms for the large-scale RIES in China, a method for RIES preliminary overall planning, focused on energy types and use, is proposed in this paper. A graph theory-based mathematical optimal model was established with the lifetime costs of the whole system as the economic goal, and an improved Prim algorithm was put forward to solve the costs of the transmission and distribution network with the dynamic weight set of pipeline flow. The model was solved by an algorithm based on the idea of a dynamic minimum spanning tree and optimal path planning. The model and method were applied in a China–U.S. low-carbon demonstration city to verify feasibility and validity. The results could help us to comprehensively integrate regional energy and accurately plan future cities.