我最近发现了Spotify今年早些时候的黑客挑战中的一个有趣问题this (Edit: Problem A)，涉及确定火车货车交汇处的转换以将火车路由回到其起点。 火车必须面对离开时的同一方向，且火车不能在轨道上倒车。
据我所知，可以将该问题建模为无向图，我们必须从某个顶点找到最短循环，或检测是否不存在这样的循环。 但是，有趣的部分在于对于一个顶点v，与v相邻的顶点取决于到达v的路径，因此从某种意义上讲，图可以被认为是有向的，尽管这个方向是依赖于路径的。
我的第一个想法是将每个节点建模为3个单独的顶点A、B和C，其中A<->B并且A<->C，然后使用广度优先搜索来构建搜索树，直到我们找到原始顶点，但是上述警告使得这变得复杂，即给定顶点的相邻点取决于我们访问的前一个顶点。 这意味着在我们的BFS树中，节点可以有多个父节点。
显然，简单的BFS搜索无法解决这个问题。我知道存在用于检测图中循环的算法。一种方法可能是检测所有的循环，然后对于每个循环，检测路径是否有效（即不反向）。
还有其他人对解决这个问题的方法有什么见解吗？
更新：我按照@Karussell在评论中提出的方法进行了尝试。 这是我在github上的解决方案。 关键是使用基于边的图来模拟情况，而不是传统的基于顶点的图。比赛中提供的输入文件已经方便地以边的形式指定，因此可以轻松地使用该文件构建基于边的图。
该程序使用两个重要的类：Road和Solver。一个Road有两个整数字段j1和j2。j1表示源交叉口，j2表示目标交叉口。每条路都是单向的，意味着只能从j1到j2行驶。每个Road还包括相邻Road的LinkedList和父Road。Road类还包括静态方法，用于在输入文件中使用的字符串和表示每个交叉口的A、B和C点之间的整数索引之间进行转换。
对于输入文件中的每个条目，我们向HashMap添加两个Road，分别代表两个交叉口之间的方向。现在，我们有了所有连接交叉口之间的道路列表。我们只需要通过A、B和C开关将道路连接在一起。如果一条Road以Junction.A结束，我们查找以Junction.B和Junction.C开头的Road，并将这些Road作为相邻项添加。buildGraph()函数返回目标交叉口（j2）为"1A" == index 0的Road。
在这一点上，我们的图已经构建完成。为了找到最短路径，我简单地使用BFS遍历图形。我们将根节点保持未标记状态，并从队列中开始排列根节点的邻接点。如果我们找到一个目标交叉口为“1A”（索引0）的道路，则我们已经找到了通过起点的最短循环。一旦我们使用每个道路的父属性重建路径，将开关适当地设置为问题所需就是一个微不足道的事情。
感谢Karussell提出此方法。如果您想将您的评论以答案形式放置，并附有简短的解释，我会接受它。也感谢@Origin。我必须承认我没有完全理解您的答案的逻辑，但这当然并不意味着它是错误的。如果有人使用您的解决方案解决了这个问题，我会非常感兴趣。
据我所知，可以将该问题建模为无向图，我们必须从某个顶点找到最短循环，或检测是否不存在这样的循环。 但是，有趣的部分在于对于一个顶点v，与v相邻的顶点取决于到达v的路径，因此从某种意义上讲，图可以被认为是有向的，尽管这个方向是依赖于路径的。
我的第一个想法是将每个节点建模为3个单独的顶点A、B和C，其中A<->B并且A<->C，然后使用广度优先搜索来构建搜索树，直到我们找到原始顶点，但是上述警告使得这变得复杂，即给定顶点的相邻点取决于我们访问的前一个顶点。 这意味着在我们的BFS树中，节点可以有多个父节点。
显然，简单的BFS搜索无法解决这个问题。我知道存在用于检测图中循环的算法。一种方法可能是检测所有的循环，然后对于每个循环，检测路径是否有效（即不反向）。
还有其他人对解决这个问题的方法有什么见解吗？
更新：我按照@Karussell在评论中提出的方法进行了尝试。 这是我在github上的解决方案。 关键是使用基于边的图来模拟情况，而不是传统的基于顶点的图。比赛中提供的输入文件已经方便地以边的形式指定，因此可以轻松地使用该文件构建基于边的图。
该程序使用两个重要的类：Road和Solver。一个Road有两个整数字段j1和j2。j1表示源交叉口，j2表示目标交叉口。每条路都是单向的，意味着只能从j1到j2行驶。每个Road还包括相邻Road的LinkedList和父Road。Road类还包括静态方法，用于在输入文件中使用的字符串和表示每个交叉口的A、B和C点之间的整数索引之间进行转换。
对于输入文件中的每个条目，我们向HashMap添加两个Road，分别代表两个交叉口之间的方向。现在，我们有了所有连接交叉口之间的道路列表。我们只需要通过A、B和C开关将道路连接在一起。如果一条Road以Junction.A结束，我们查找以Junction.B和Junction.C开头的Road，并将这些Road作为相邻项添加。buildGraph()函数返回目标交叉口（j2）为"1A" == index 0的Road。
在这一点上，我们的图已经构建完成。为了找到最短路径，我简单地使用BFS遍历图形。我们将根节点保持未标记状态，并从队列中开始排列根节点的邻接点。如果我们找到一个目标交叉口为“1A”（索引0）的道路，则我们已经找到了通过起点的最短循环。一旦我们使用每个道路的父属性重建路径，将开关适当地设置为问题所需就是一个微不足道的事情。
感谢Karussell提出此方法。如果您想将您的评论以答案形式放置，并附有简短的解释，我会接受它。也感谢@Origin。我必须承认我没有完全理解您的答案的逻辑，但这当然并不意味着它是错误的。如果有人使用您的解决方案解决了这个问题，我会非常感兴趣。