BFS주기 감지

Question

누군가가 BFS를 사용하여 단계 의사 코드에 의해 지시/방향없는 그래프의주기를 검색 할 수 있습니까?

O (| V | + | E |) 복잡도를 얻을 수 있습니까?

지금까지 DFS 구현 만 보았습니다.

Answer 1

비 재귀 DFS 알고리즘을 사용하여 노드에 대한 스택을 대기열로 바꿔 BFS 알고리즘을 얻을 수 있습니다. 그것은 간단합니다 :

q <- new queue // for DFS you use just a stack 
append the start node of n in q 
while q is not empty do 
    n <- remove first element of q 
    if n is visited 
     output 'Hurray, I found a cycle' 
    mark n as visited 
    for each edge (n, m) in E do 
     append m to q 

BFS 각 노드를 방문하여 한 번만 각 에지, 당신은 O의 복잡성을 가지고 있기 때문에 (| V | + | E를 |).

Answer 2

나는 BFS 알고리즘이 완벽하다는 것을 알았다. 시간 복잡도는 동일합니다.

Cycle-With-Breadth-First-Search(Graph g, Vertex root): 

    create empty set S 
    create empty queue Q  

    root.parent = null 
    Q.enqueueEdges(root)      

    while Q is not empty: 

     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) 
      else //We found a cycle 
       n.parent = current 
       return n and current 

내가 사이클 검출 단지 다른 사람의주기 블록을 추가하고 표적 탐지를위한 원래의 경우 도달 목표 블록을 제거 :

당신은 (위키 백과에서 수정 됨)이 같은 것을 원한다. 전체적으로 동일한 알고리즘입니다.

정확한주기를 찾으려면 n과 현재에 대한 공통 조상을 찾아야합니다. 가장 낮은 값은 O (n) 시간에 사용할 수 있습니다. 주기가 알려지기 때문입니다. 조상을 n 및 현재로. 전류와 n이 연결됩니다. 사이클과 BFS에 대한 자세한 정보를 들어

는 https://stackoverflow.com/a/4464388/6782134