next up previous contents index CD CD Algorithms
Next: Search Pruning Up: Backtracking Previous: Constructing All Permutations

Constructing All Paths in a Graph

Enumerating all the simple paths from to t through a given graph is a somewhat more complicated problem than listing permutations or subsets. Unlike the earlier problems, there is no explicit formula that counts the number of solutions as a function of the number of edges or vertices, because the number of paths depends upon the structure of the graph.  

Figure: The search tree enumerating all simple paths from vertex 1 in the graph  

Since the starting point of any path from to t is always , tex2html_wrap_inline25709 must be tex2html_wrap_inline25711 . The set of possible candidates for the second position are the vertices v such that (,v) is an edge of the graph, for the path wanders from vertex to vertex using edges to define the legal steps. In general, tex2html_wrap_inline25715 consists of the set of vertices adjacent to tex2html_wrap_inline25717 that have not been used in the partial solution A. We can report a successful path whenever tex2html_wrap_inline25719 . The solution vector A must have room for all n vertices, although most paths are likely to be shorter than this. Figure gif shows the search tree giving all paths from a particular vertex in an example graph.

Mon Jun 2 23:33:50 EDT 1997