0

试图在java中编写代码。请建议任何适用于这种情况的算法。输入是：

Col A   Col B
A       B
A       C
B       D
C       A
C       B
C       E
D       A
D       B
E       A

我正在尝试进行组合，例如输出：

A   B   D   A       
A   C   A           
A   C   B   D   A   
A   C   E   A       
B   D   B           
C   A   B   D   A   C
C   A   C           
C   B   D   A   C   
C   E   A   C

|
|
|

等等。输出的起点和终点应该相同。

另一种看待它的方式是，你从节点 A 开始，你必须回到节点 A，所以你的路径是从 A 到 B，然后是 B 到 D（因为从 B 你只能去一个节点，即D），然后 D 到 A。所以，col A 和 Col B 为您提供了可能的路径，例如从 A 到 B 和 C，而不是 D 和 E。我希望这会有所帮助。另外，有什么办法可以限制没有。解决方案的节点数？

请提出一些想法。

4

2 回答 2

0

您需要使用递归，并且当您通过数据进行递归时，您需要标记您访问过的位置，这样您就不会无限地走同一条路径，

于 2013-03-17T20:13:06.760 回答
0

根据您的数据，您有五个不同节点的集合 - A、B、C、D 和 E。

如果我们将它们组合在一起，那么我们会得到与什么相关的映射：

A:  [B, C]
B:  [D]
C:  [B, E]
D:  [A, B]
E:  [A]

上面表示一个稀疏图。除了 B->D->B，一个节点不会直接从另一个节点连接回自身。

这是我如何处理它的流程。

  • 将 aMap<String, List<String>用于我到达的主节点，以及该节点连接到的边。

  • 选择一个起始节点a。将其链接放入堆栈。

  • 检查结束节点是否与开始节点相同。
    • 如果是，你就完成了 - 从堆栈中弹出元素并获取你的路径。
    • 如果不是，则从堆栈中弹出第一个元素并将其链接推入堆栈。从检查重复。
  • 如果没有什么可以弹出，那么就没有从a到a 的路径。

这种遍历方式是深度优先搜索。您将更深入地了解图表，直到您到达您的路径或用尽您的选择。

于 2013-03-17T20:23:28.130 回答