我正在尝试找到所有长度不超过给定值的简单路径，并尝试使用 BFS 来解决这个问题。但是，我不确定要使用的具体算法。似乎 BFS 无法轻松解决这个问题。我发现的所有问题都是关于在两个给定顶点之间寻找路径。

但是，我想知道如何找到有向图中从给定顶点开始的所有长度不超过给定 k 的简单路径。不允许有循环。

k 长度表示 k 跳，而不是路径的权重。

例如，我们有 k = 3，并且给定顶点 1，我们想要找到长度为 k = 1、k = 2、k = 3 的路径。

当 k = 1 时，我们有路径 12 和 13；当 k = 2 时，我们有路径 132 和 134；当 k = 3 时，我们找不到合适的路径。

我可以使用什么算法来解决这个问题？

1

  • 1
    @trincot 你的建议很有帮助。我会发布一个关于添加内容的新问题！


    – 


最佳答案
3

您可以使用深度优先遍历来实现这一点。递归函数是实现这一点的自然选择。它会递归到深度k，然后生成它所遍历的路径。在每次递归调用时，请确保不要将已经在路径上的节点添加到路径上。当您退出递归调用时，相应地缩短路径。

下面是 JavaScript 中的一个实现，其中递归函数以邻接表（表示图）、当前节点、的值k和路径作为集合（有序哈希集）作为参数。

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    if (k == 0) return yield [...path, node]; // We have a result
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with k=1, k=2 and k=3:
for (let k = 1; k <= 3; k++) {
    console.log("results for k =", k);
    for (const path of genPaths(adj, "1", k)) {
        console.log("  ", ...path);
    }
}
console.log("done");

扩展它…

上述函数返回精确 k长度的路径，主代码使用它来获取几种不同长度的路径。如果您也始终对所有较短的路径感兴趣，甚至包括大小为 0 的路径（仅起始节点），那么您可以扩展该函数以通过一个顶级调用完成所有操作：

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    yield [...path, node]; // We have a result (0 <= path size <= k)
    if (k == 0) return;
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with size <= 3:
for (const path of genPaths(adj, "1", 3)) {
    console.log("  ", ...path);
}
console.log("done");

请注意，路径的大小以其上的边数表示，因此 [1] 是长度为 0 的路径，[1, 3] 是长度为 1 的路径，…等等。

如果要排除长度为 0 的路径，则只需在语句中添加一个条件yield：

    if (path.length > 0) yield [...path, node];

9

  • 嘿，谢谢！这很有帮助！我的图表真的很大。如果我们使用 DFS/递归，可能会导致堆栈溢出。我可以使用 BFS 吗？


    – 

  • 最大递归深度等于最大路径长度k。


    – 

  • @beaker 你说得对。我明白了！谢谢！


    – 

  • 我认为 DFS 比 BFS 更适合这种情况。这最终是你正在寻找的吗？如果您仍有疑问，请告诉我…


    – 

  • @trincot 我认为 DFS 的主要缺点在于重复计算。例如，k = 1 的路径是 k = 2 的前缀路径。如果我们分别计算 k = 1、2 和 3 的路径，效率就不高了。对吗？


    – 

以下是 Yen 算法的伪代码

IMPORT graph, source and sink
CLEAR vShortestPaths
calculate shortest path from source to sink, add to vShortestPaths
WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE

要查找图中的所有路径：

Set vertices into fixed order ( input order is fine )
LOOP I over vertices
   LOOP J over the (J+1)the to the last vertex
       Apply Yen to I,J vertex pair

7

  • 谢谢！但是，该算法考虑了路径的权重。我的问题中的“长度”等于路径的跳数，而不是权重。


    – 

  • 将每条边的权重设置为 1。


    – 

  • 我只是发现这个算法的输入需要原点顶点和目标顶点，这与我的问题不同。


    – 

  • 2
    Yen 的算法用于计算 k 条最短路径。这与 OP 提出的问题完全不同。


    – 

  • 1
    是的，我知道要实现这一点需要进行修改，但我的问题是为什么？你通过多次解决一个更复杂的问题来回答一个简单的问题。那个“计算最短路径”步骤是如何实现的？可能是用 Dijkstra 算法吧？因此，每次执行 Dijkstra 算法时，你都会计算从一个源到剩余图中所有其他顶点的最短路径，然后丢弃除一个之外的所有顶点。然后重新执行，直到路径变得太长。然后为每个接收器重新执行所有这些操作。但是 Dijkstra 在无权图上的算法是什么？DFS。


    – 

可以修改和调整在第 14.3.1 – 14.3.2 节中使用的 DFS 遍历的回溯*版本来解决这个问题。

我们还希望通过使用有序哈希表（这意味着您的顶点必须是可哈希的）来跟踪访问过的顶点和相应的树边（或发现的边），从而防止循环遍历（通过使用邻接图来表示图，我们可以在O（1）时间内查询遍历的顶点并省略后边）。

这最终将生成可通过遍历图中最多k -1 条边到达的（隐含的）（或在无向图的情况下为），通过在起始顶点s上调用 DFS，然后在指定的k范围内对所有偶然发现的边顶点递归调用 DFS 。

* 我们为每个有效的递归 DFS 调用（当遍历的边< k时）填充一个并发路径累加器，然后在递归展开时回溯并弹出相应的回缩边（当遍历的边>= k时触发，直到再次遍历和累积新的边）。

以下解决方案使用 Goodrich 等人提出的邻接图表示图（第 635-637 页）。为简洁起见，可以在此处找到与此算法 100% 兼容且无依赖关系的图实现：。

方法Graph.insert_vertex()、Graph.insert_edge()、Edge.opposite()全部在O (1) 时间Edge.endpoints()内运行，除了需要O (传出度( v )) 时间。Graph.incident_edges(v)

最初，在最坏情况下（当找到在k 条边中可到达的顶点需要遍历整个图时）klen_dfs()应该花费O (n) 时间。但是，保存每条唯一路径（使用线）会引起一些必要的重新计算，每遍历一条k长度的路径大约需要求和( k ) 次操作，即n k ×求和( k )，其中n k是遍历k条边可到达的顶点数。总体而言，在最坏情况下需要O (( n k × k 2 ) + n) 时间。path_array.append(p[:])klen_dfs()

from collections import OrderedDict
from typing import List
from graph import Graph


def init_graph():
    G = Graph(directed=True)

    v1 = G.insert_vertex(1)
    v2 = G.insert_vertex(2)
    v3 = G.insert_vertex(3)
    v4 = G.insert_vertex(4)

    G.insert_edge(v1, v2)
    G.insert_edge(v1, v3)
    G.insert_edge(v3, v2)
    G.insert_edge(v3, v4)
    G.insert_edge(v4, v3)

    return G, v1


def klen_dfs(G: Graph, s: Graph.Vertex, k: int):
    """Report all paths (edge lists) less than length k.
    G - Adjacency Map Graph ADT
    s - Starting vertex
    k - Path length limit (actual limit = k-1)
    """
    discovery_edges: OrderedDict[Graph.Vertex, Graph.Edge] = OrderedDict()
    path_accummulator: List[Graph.Edge] = [ ]
    path_array: List[List[Graph.Edge]] = [ ]

    def dfs(g: Graph, u: Graph.Vertex, discovered, klen, p):
        """Traditional DFS with addtional params.
        u - A vertex in G
        p - Concurrent path array of less than k edges
        """
        if klen < k:
            for e in g.incident_edges(u, outgoing=True):
                v = e.opposite(u)
                if not discovered.get(v):   # Cyclic traversal prevention
                    discovered[v] = e
                    p.append(e)
                    path_array.append(p[:])
                    dfs(g, v, discovered, klen + 1, p)
                    p.pop()
                    discovered.pop(v)

    dfs(G, s, discovery_edges, 1, path_accummulator)
    return path_array


if __name__ == "__main__":
    # For graph produced by init_graph(), all k >= 3 has same results
    for K in range(1,4):
        digraph, start = init_graph()
        paths = klen_dfs(digraph, start, K)
        formatted_paths = []
        for path in paths:
            formatted_path = []
            for edge in path:
                endpoints = edge.endpoints()
                formatted_path.append((
                    endpoints[0].element(), endpoints[1].element()))
            formatted_paths.append(formatted_path)
        print(f"ALL paths when k = {K} (i.e of length {K-1} < k length)")
        print(*formatted_paths, sep="\n")
        print()

输出：

ALL paths when k = 1 (i.e of length 0 < k length)

ALL paths when k = 2 (i.e of length 1 < k length)
[(1, 2)]
[(1, 3)]

ALL paths when k = 3 (i.e of length 2 < k length)
[(1, 2)]
[(1, 3)]
[(1, 3), (3, 2)]
[(1, 3), (3, 4)]

当s =1时，长度小于k =3的简单有效路径的可视化

其他考虑：严格k长度路径

修改，我们可以选择仅报告长度为k的路径，方法是用 替换嵌套函数中的行dfs()：path_array.append(p[:])。if klen == k-1: path_array.append(p[:])

这将时间复杂度从O (( nk × k 2 ) + n) 降低到O (( nk × k ) + n ) ，并产生以下输出：

ALL paths when k = 1 (i.e of length 0 < k length)

ALL paths when k = 2 (i.e of length 1 < k length)
[(1, 2)]
[(1, 3)]

ALL paths when k = 3 (i.e of length 2 < k length)
[(1, 3), (3, 2)]
[(1, 3), (3, 4)]

1

  • 1
    非常感谢！我需要花时间来理解代码，因为我很久没用过 Python 了。


    –