BFS Tree and x-y Shortest Paths Tree

摘要

The Breadth-First-Search algorithm and the Depth-First-Search algorithm belong to the most used searching algorithms. The spanning trees gained by the algorithms have special and interesting properties. Using them we can obtain important statements enabling to formulate various other algorithms. In the paper the statements, based on the Breadth-First-Search, concerning circles with the given properties will be formulated at first. Then a new concept x-y Shortest Paths Tree, i.e. tree that contains all the shortest paths from the vertex x to the vertex y in the given undirected graph, will be formulated as well as an algorithm using the x-y Shortest Paths Tree to determine all the shortest paths between the two given vertices.