        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 , must be . 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, consists of the set of vertices adjacent to that have not been used in the partial solution A. We can report a successful path whenever . The solution vector A must have room for all n vertices, although most paths are likely to be shorter than this. Figure shows the search tree giving all paths from a particular vertex in an example graph.

Algorithms
Mon Jun 2 23:33:50 EDT 1997