scheme - determine whether undirected graph has path between two vertices

Question

I need a function which determines whether a path exists between vertices.

Input:

• undirected graph as a list
• two vertices

For example:

(is_it_a_path? '(2 ((1 2) (3 4))) 1 4)   ;; returns true

The function also needs to be tail recursive.

How do I do this?

Answer 1

The (free, online) textbook How To Design Programs has several sections that may be helpful to you.

You say that the solution must be tail-recursive. If you mean that all calls to the search procedure must be in tail position, then you're going to have to keep track of visited-nodes and paths-to-nodes explicitly.

Next: I'm confused by your example; it looks like the input is... a list of length two containing a goal node and some representation of the graph? But... no, I'm still confused.

You need to explain how what the input means---for instance, how are graphs represented as inputs to your function?