algorithm - 距离 K 的顶点

Question

给定一个图G(V,E)和一个顶点v ，我如何找到通过长度正好为k的简单路径（路径上没有顶点重复）可到达的所有顶点。

邻接矩阵的幂给出了顶点之间的路径数，但它包括非简单路径。

这个问题可以在多项式时间内解决吗？如果没有，是否有任何已知的近似算法。任何指向文学的指针都会很棒。

Answer 1

我只回答第一个问题：“它可以在多项式时间内解决吗？”。

假设它在多项式时间内是可解的。然后解决它k=|V|-1并选择任何结果顶点。删除这个顶点并解决这个问题k=|V|-2。生成的一组顶点应包含至少一个连接到最后一个删除顶点的顶点。移除这个顶点并继续处理k=|V|-i直到剩下一个起始顶点。您刚刚使用多项式时间算法找到了原始图的哈密顿路径。

由于哈密顿路径问题是 NP 完全的，因此 OP 中的问题也不太可能在多项式时间内解决。

Answer 2

k下面介绍的算法将找到与起始节点的最小距离等于的节点列表v。EG：给定一个三角形图 v、A 和 B，如果：

• k为 0，则结​​果为v
• k为 1，则结果包含A和B
• k为 2 或更多，则结果为empty

伪代码：

FindNodesWithShortestPath_K(G, v, k):
    create empty list R
    create empty queue Q

    mark v as visited
    set v.distance to 0
    add v to Q

    while Q is not empty:
        t <- dequeue node from Q
        if t.distance == k:
            add t to R
        else if t.distance > k:
            break
        else                
            for all neighbors u of t:
                if u is not marked as visited:
                    mark u as visited
                    u.distance = t.distance + 1
                    enqueue u onto Q

    return result

笔记：

• 检查节点是否被标记为已访问保证简单的路径
• 节点的初始距离不相关
• 如果 t.distance == k，则 t 属于 R 并且 t 邻居（不在 Q 中）不属于
• 如果 t.distance > k，那么即使 Q 不为空，算法也会停止。给定算法实现，Q中节点的距离是非递减的
• R 和 Q 上的操作可以在 O(1) 中运行，具体取决于实现。该算法的最坏情况为 O(|E| + |V|)