寬度優先遍歷指向vs無向圖

Question

定向和無向圖上的bfs如何在實現中有所不同。

我在網上發現了下面的僞代碼。我很喜歡無向圖。但無法弄清楚如何爲有向圖實現它。

frontier = new Queue() 
    mark root visited (set root.distance = 0) 
    frontier.push(root) 
    while frontier not empty { 
    Vertex v = frontier.pop() 
    for each successor v' of v { 
    if v' unvisited { 
     frontier.push(v') 
     mark v' visited (v'.distance = v.distance + 1) 
    } 
    } 
    } 

Answer 1

僞代碼的實現是一樣的，不同之處在於successor概念將意味着鄰居爲無向圖，但孩子（或類似）的有向圖。