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

Question

我有一个有向图，看起来有点像这样。所有边都是单向的，存在循环，有些节点没有子节点。

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

• 起始节点是随机选择的，它遍历其子节点，并且访问的节点保留在某个位置以返回末尾的路径
• 可以再次访问相同的节点
• 如果它到达没有子级的节点，它将遍历具有未探索子级的最新节点。如果遍历了从起始节点开始的所有可能路径，请尝试从其他节点开始。（我认为这种方法可以确保探索所有可能的路径）
• 当访问的节点数达到 n 并返回路径时，遍历停止
• 如果未找到长度为 n 的路径，则返回“无有效路径”

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

Answer 1

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

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]))

Answer 2

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

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