确定无向图具有两个顶点之间的路径 [英] determine whether undirected graph has path between two vertices

问题描述

我需要一个函数来确定顶点之间是否存在路径。

输入：

• 无向图列表


• 两个顶点

例如：

 （is_it_a_path？'（2（（1 2）（3 4）））1 4）;;返回true 
  

该函数也需要是递归的。

我该怎么做？

解决方案

（免费，在线）教科书如何设计程序有几个部分可能对您有所帮助。

你说该解决方案必须是尾递归的。如果您的意思是所有对搜索过程的调用都必须处于尾部位置，那么您将必须明确地跟踪访问节点和路径到节点。

下一步：我很迷惑你的榜样;它看起来像输入是...一个长度为2的列表，包含一个目标节点和图形的某种表示形式？但是......不，我仍然感到困惑。

您需要解释输入意味着什么 - 例如，图表如何表示为您的输入功能？

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?

解决方案

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?

这篇关于确定无向图具有两个顶点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！