我最近遇到了ojit_，这是今年早些时候Spotify的黑客挑战中的一个有趣问题，涉及确定火车卡车路口的转换以将火车送回到起点。火车必须以与左方向相同的方向到达，火车永远不能在铁轨上倒退。
据我了解，可以将问题建模为无向(？)图，其中我们必须从某个顶点中找到最短的周期，或者检测到不存在这样的周期。但是，有趣的是，对于顶点v，与v相邻的顶点取决于通向v的路径，因此在某种意义上，可以将图形视为有向的，尽管该方向与路径有关。
我的第一个想法是将每个节点建模为3个单独的顶点A，B和C，其中A B和A C，然后使用广度优先搜索来构建搜索树，直到找到原始树为止顶点，但是由于上述警告而变得复杂，即给定顶点的邻接取决于我们访问的先前顶点。这意味着在我们的BFS树中，节点可以有多个父节点。
显然，简单的BFS搜索不足以解决此问题。我知道有一些算法可以检测图中的周期。一种方法可能是检测所有周期，然后对于每个周期，检测路径是否有效。 (即，不反转方向)
是否有其他人对解决此问题的方法有任何见解？
更新:
我遵循@Karussell在评论中建议的方法。
this (Edit: Problem A)
诀窍是使用基于边缘的图而非传统的基于顶点的图对情况进行建模。竞赛中提供的输入文件已经方便地根据边进行了指定，因此可以轻松地使用该文件来构建基于边的图形。
该程序使用两个重要的类:Road和Solver。道路具有两个整数字段j1和j2。 j1代表源结，j2代表目标结。每条道路都是单向的，这意味着您只能从j1到j2行驶。每条道路还包括相邻道路和父道路的链接列表。 Road类还包括静态方法，用于在输入文件中使用的字符串和表示每个结点处的A，B和C点的整数索引之间进行转换。
对于输入文件中的每个条目，我们将两个Roads添加到HashMap中，两个路口之间的每个方向都添加一个Road。现在，我们有了在路口之间延伸的所有道路的列表。我们只需要通过A，B和C开关在交叉路口将道路连接在一起即可。如果道路在Junction.A处结束，我们将查找从Junction.B和Junction.C处开始的道路，并将这些道路添加为相邻道路。 buildGraph()函数返回Road，其目标结点(j2)为“1A” ==索引0。
至此，我们的图已构建完毕。为了找到最短的路径，我仅使用BFS遍历图形。我们保留根的未标记状态，并从排队根的邻接处开始。如果找到目标交界处为“1A”(索引0)的道路，那么我们发现到起点的周期最短。一旦我们使用每个Road的父级属性重建路径，便可以轻松地根据问题中的需要设置开关。
感谢Karussell提出了这种方法。如果您想以简短的解释将您的评论放在回答表中，我将接受。还要感谢@Origin。我必须承认，我没有完全遵循您的回答的逻辑，但这当然不是说它是不正确的。如果有人使用您的解决方案解决了这个问题，我将非常有兴趣看到它。
最佳答案
正如我的评论所建议的那样:我认为您可以通过edge based graph或通过an improvement来解决此问题，ojit_a或多或少是基于“增强”节点的图。
细节:
除了可以将“状态”(定向!)建模到图中之外，您还可以为每个结点分配可能的结果-现在，算法需要更聪明，并且需要根据您的早期状态(包括方向)。我认为，这是基于“增强型”节点的图的主要思想，该图应减少内存密集性(在您的情况下不那么重要)。