有向循环图遍历寻找一定长度的路径

Question

我有一个看起来有点像的有向图 this。所有边都是单向的，环存在，部分节点没有children.

我想要一种遍历算法，其目标是在图中的任意位置找到一条长度为 n 个节点的路径。该算法应执行以下操作：

起始节点是随机选择的，它遍历它的 children，并且访问过的节点保留在某处到 return 路径的最后
可以再次访问相同的节点
如果到达没有children的节点，则遍历最近未探索的节点children。如果从起始节点开始的所有可能路径都被遍历，则尝试从其他节点开始。（我认为这种方法确保探索所有可能的路径）
当访问的节点数达到 n 且路径为 returned
如果找不到长度为 n 的路径，则 returns“没有有效路径”

我不确定是否已经存在适用于此的算法。大多数搜索算法似乎处理寻找最短路径、MST，并且不能访问相同的节点。像 A* 和 Dijkstra 这样的寻路算法似乎对我的需求来说过于复杂。我可能需要其中之一的修改版本，但不确定要使用哪一个。

Answer 1

听起来你只是想要一个简单的递归算法。这是一些基本的伪代码。

find_path(node, n):   
   if n == 1:
       yield [node]
       return
   for each child of node n:
       for each path in find_path(child, n - 1):
           yield [node] + path

Answer 2

我会使用 Node 和 Edge 的每个节点跟踪所有连接的边。而边的长度和它连接到的节点的长度的Edges cheap跟踪。

class Node(object):
    def __init__(self, identity):
        self.id = identity
        self.edges = set()

    def __str__(self):
        return f"node <id: {self.id}, edges: {self.edges}"
    __repr__=__str__


class Edge(object):
    def __init__(self, _from, to, length=1):
        _from.edges.add(self)
        self.to = to
        self.len = length

    def __str__(self):
        return f"edge <length: {self.len}, to: {self.to}"

    def __repr__(self):
        return f"edge <length: {self.len}>"

而不是像这样找到一定长度的路径

def getPathOfLength(nodes, length):
    for node in nodes:
        path = subGetPathOfLength(node, length)
        if not path is None:
            return path

def subGetPathOfLength(node, length):
    if length==0:
        return []
    
    for edge in node.edges:
        path = subGetPathOfLength(edge.to,
                                  length-edge.len)
        if not path is None:
            return [node] + path
    return None

像这样创建连接图后

nodes = []
for idx in range(8):
    nodes.append(Node(idx))

edges = []

edges.append(Edge(nodes[0], nodes[3]))
edges.append(Edge(nodes[3], nodes[4]))
edges.append(Edge(nodes[4], nodes[0]))

edges.append(Edge(nodes[7], nodes[0]))
edges.append(Edge(nodes[6], nodes[7]))
edges.append(Edge(nodes[2], nodes[6]))
edges.append(Edge(nodes[2], nodes[3]))


edges.append(Edge(nodes[1], nodes[3]))
edges.append(Edge(nodes[3], nodes[5]))

有向循环图遍历寻找一定长度的路径

Directed cyclic graph traversal to find a path of certain length

python

algorithm

graph-theory

graph

path-finding