Подсчет узлов и дуг в алгоритме BFS

Question

В DFS вы можете подсчитать элементы, инициализируя два счетчика и увеличивая их в процедуре DFS-VISIT (+1 узел при каждом вызове процедуры и +1 дуга каждый раз, когда список смежности исследовал). Мне было интересно, как получить тот же результат в BFS. Это псевдокод BFS из «Введение в алгоритмы» Кормена, где G - это граф, s - исходный узел, d - расстояние, а π - узел отца. Как я могу изменить его, чтобы получить количество узлов и дуг в G?

BFS(G, s) 
    for each node u ∈ G.V - {s} 
     u.color = white 
     u.d = ∞ 
     u.π = NIL 
    s.color = GRAY 
    s.d = 0 
    s.π = NIL 
    Q = Ø 
    ENQUEUE(Q, s) 
    while Q != Ø 
     u = DEQUEUE(Q) 
     for each v ∈ G.Adj[u] 
       if v.color == WHITE 
         v.color = GRAY 
         v.d = u.d + 1 
         v.π = u 
         ENQUEUE(Q, v) 
     u.color = BLACK 

Answer 1

Ну, как список смежности обход и новая вершина (узел) открытие сделаны в финале во время цикла вашего псевдокода. Итак, что-то вроде приведенной ниже модификации может работать.

numArcs = 0 
numNodes = 0 
while Q != Ø 
    u = DEQUEUE(Q) 
    numNodes += 1 
    for each v ∈ G.Adj[u] 
      numArcs += 1 
      if v.color == WHITE 
        v.color = GRAY 
        v.d = u.d + 1 
        v.π = u 
        ENQUEUE(Q, v) 
    u.color = BLACK 

Обратите внимание, что если вы хотите, чтобы сосчитать все дуги, то приращение numArcs должно быть вне сферы действия, если утверждения, что следует за ним, как если оператор только вводится, когда узел назначения не ранее помещён ,

Обратите внимание, что этот алгоритм дает только количество дуг и узлов в подключенном компоненте, включая начальный узел s. Таким образом, если ваш алгоритм BFS не изменен для обработки графика, имеющего несколько подключенных компонентов, этот алгоритм не будет обнаруживать все узлы и дуги в графе, который не связан.