0

我创建了一个有 6 个顶点的无向图，在视觉上表示如下：http: //i.imgur.com/EtQyspG.png

我想编写一个脚本，它可以从起点找到所有路径，而无需重新访问同一个节点，也没有给定的终点。

我看过的 BFS、DFS、A* 算法的每个示例都需要一个最终目标节点。但是，在较大的图表上，找到从 A 点到 Z 点的所有可能路径可能是 NP 困难的。因此，我想找到在设定的移动次数内可实现的所有目的地的所有路径（在此图例如 -- 3 次移动 == 路径中的 4 个最大顶点）

我使用 PHP 数组对图形进行了编码，每个键都是一个顶点，其数组包含相邻点：

<?php

$graph[1] = array(2,6);
$graph[2] = array(1,4);
$graph[3] = array(4,5);
$graph[4] = array(2,3,6);
$graph[5] = array(6,3);
$graph[6] = array(1,5,4);

不过，我不知道以这种方式执行路径搜索的算法。我想要的输出是这样的：

Path 1: 1,2
Path 2: 1,2,4
Path 3: 1,2,4,3
Path 4: 1,6
Path 5: 1,6,4,3
Path 6: 1,6,5
Path 7: 1,6,5,3

我编写所需的代码没有问题，但是算法/函数的必要步骤（假设树遍历递归？）很难理解。

问题：应该使用什么方法/算法来执行此操作，您是否有一个示例（或至少是伪代码）来说明在给定图形输入数组的情况下它是如何工作的？

4

2 回答 2

0

好吧，在密集图 (|E| ~ O(|V|^2)) 中，输出的大小是最大移动量的指数，任何程序都需要至少与它的数据大小呈线性关系的时间必须输出。

完成您所要求的最简单的方法是采用香草递归 DFS 算法并对其进行修改，以便

1）顶点堆栈维护在一个实际的堆栈中（我的意思是数组/向量/Python列表/等等，无论你在PHP中拥有什么等价物）。调用前插入目标顶点，调用返回后弹出。

2）当达到深度k时，函数将堆栈打印到输出并返回

3) 递归函数在返回之前“取消标记”当前顶点

不过，我无法专门为您提供 PHP 方面的帮助。

于 2013-02-24T22:07:27.983 回答
0

单一起点和分支告诉您构建一棵树。这只是深度有限的树搜索。在每个级别，您都需要修剪您已经访问过的节点。伪代码在wiki文章中

于 2013-02-24T22:01:00.443 回答