对于给定的图G =(V，E)和一个边E∈E，设计一个O(n M) - 时间算法，以查找包含e的最短循环

Question

试图理解图形并非常困难。我知道如何找到最短的路径，但不确定如何找到最短的周期并仍然在O（n m）时间？

Answer 1

最短的循环包含e

bfs是完美的。一个周期将是目标。时间复杂性相同。

您想要这样的东西（从Wikipedia编辑）：

Cycle-With-Breadth-First-Search(Graph g, Edge e):
    remove e from E
    root is b where e = (a,b)
    create empty set S
    create empty queue Q      
    root.parent = a
    Q.enqueueEdges(root)                      
    while Q is not empty:
        if current = a
            return current
        current = Q.dequeue()
        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)

有关循环和BFS的更多信息，请阅读此链接https://stackoverflow.com/a/4464388/6782134