Description

It is shown that any tree of a connected graph G is a depth-first-search (DFS)-tree of one of its 2-isomorphic graphs if, and only if, G is a series-parallel graph, where two graphs are said to be 2-isomorphic if they have the same set of edges as well as the same set of circuits. Only non-separable graphs are considered. A basic theorem on series-parallel graphs is given, and the main theorems are discussed. The shortest path problem based on the data structure has become one of the hot research topics in graph theory. As the basic theory of solving this problem, Dijikstra’s algorithm has been widely used in engineering calculations. Aiming at the shortcomings of traditional Dijikstra’s algorithm, this paper has proposed an optimization method which has mainly improved the nodes selection of the shortest path and data storage structure and organization. Through comparison and analysis, the improved algorithm has been obtained, which has reduced the storage space, improved the operational efficiency and has a better applicability in the shortest path calculation.