查找无向图路径的算法

-3

在无向图中查找路径的简单算法是什么？查找无向图路径的算法

2012-02-27 IAQ

在过去的一两天内，有一组与图形相关的Scheme问题进入Stack Overflow。示例：http://stackoverflow.com/questions/9426788/depth-first-search-dfs-for-undirected-graphs。这是一个功课问题吗？ – dyoo 2012-02-27 04:13:44

是的，但另一个不是我的帖子 – IAQ 2012-02-27 04:31:30

强烈建议：请参阅：http://www.htdp.org/2003-09-26/Book/curriculum-ZH-35.html#node_chap_28以及http ：//www.htdp.org/2003-09-26/Book/curriculum-ZH-38.html – dyoo 2012-02-27 04:44:18

此问题的答案依赖于您的图形表示。典型的算法是Dijkstra算法（注意，这个算法会找到最短路径，但是工作正常）。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

这是一个相当简单的算法来实现，也可能是寻路算法的最直观之中。

来源

2012-02-27 01:52:31

我必须写的函数只是假设有或没有路径时返回true或false。此外，该图被定义为 is_path？ '（3（（1 2）（2 3））1 3）其中3是顶点数，（（1 2）（2 3））是边。然而，顶点的数量是可选的。我看着Dijkstra的算法，但是我仍然完全迷失。进一步的帮助将不胜感激。 – IAQ 2012-02-27 01:57:31

Dijkstra算法的本质是它使用图边之间的一种传递闭包。例如，在第一次迭代中，您将看到，如果a - > b和b - > c，然后是a - > c，则基本上会继续此操作，直到发现图形中两个节点之间存在路径，或者尝试所有可能的边缘之间的不同方式，并发现没有可能的路径。布鲁斯指出你在Scheme中实现这一点。 – 2012-02-27 02:04:22

查找路径是否存在的最简单方法是实施depth-first search。如果您在Scheme中执行了其他类型的递归编程，深度优先搜索将非常自然。这个想法是，对于每个节点，如果它是你完成的目的地;否则你会在每个孩子身上复发。

唯一的问题是您需要跟踪遍历期间已经访问过的节点，这样可以避免两次访问同一个节点;否则如果你有一个图A < - > B < - > C并且你正在检查A是否连接到C，那么你可能无限循环从A到B，然后B到A，然后A到B，永远等等。

来源

2012-02-27 02:20:50 jacobm

查找无向图路径的算法

回答

相关问题