无向图的深度优先搜索 (DFS) [英] Depth-first search (DFS) for undirected graphs

问题描述

我正在查看这个.

如果给我一个包含边数(图形)、边对、起点和终点的列表，我如何确定是否存在路径?

If I were just given a list that contained the number of edges (graph), pair of edges, a origin and a destination, how would I figure out if there is or isn't a path?

我有一些想法，但在开始计划方面需要一些帮助.

I have some idea, but just need a bit of help in terms of starting in scheme.

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

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

下面的 4 是顶点数，(1 2)... 边也是，1 是起点，4 是终点.基本上，您正在查看以下定义的图中是否存在从 1 到 4 的路径.我希望这能澄清我的意思.

In the following 4 is the number of vertices, (1 2)... and so are are the edges and 1 is the start and 4 is the end. Basically from these you are looking at whether there is a path from 1 to 4 in the following defined graph. I hope that can clarify what I mean.

推荐答案

您是否看到 John Clements 之前对如何设计程序的回复?它有一个章节关于如何设计处理图形的程序.

Did you see John Clements's earlier response to look at How to Design Programs? It has a Chapter on how to design programs that deal with graphs.

作为元答案:您提出的问题，即如何开始解决您不熟悉的问题，是 HtDP 书籍的核心.你看过吗?它本质上是对 Polya 的 How To Solve It 的改编，但专为编写计算机程序而不是数学证明而量身定制.第二版草案可能更容易阅读.

As a meta-answer: the question you're asking, about how to get started on a problem that you're unfamiliar with, is the heart of the HtDP book. Have you looked at it? It's essentially an adaptation of Polya's How To Solve It, but tailored for writing computer programs rather than math proofs. The Second edition draft may be easier to read.

这篇关于无向图的深度优先搜索 (DFS)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！