BFSのノードと円弧の計算アルゴリズム

Question

DFSでは、DFS-VISITプロシージャで2つのカウンタを初期化し、それらをインクリメントすることで要素を数えることができます（プロシージャが呼び出されるたびに+1ノード、隣接リストが探検）。私はBFSで同じ結果を得る方法を考えていました。 これはCormenの「Introduction to Algorithms」の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

まあ、隣接リストの探索と新しい頂点（ノード）探索の両方が、あなたの擬似コードの最後のwhileループで行われます。したがって、以下のような修正が働く可能性があります。

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の増分は、宛先ノードが以前にエンキューされていないときのステートメントにのみ入力された場合にそのように、それを次のif文の範囲外であることに注意してください。

このアルゴリズムは、開始ノードsを含む接続コンポーネントのアークとノードの数だけを示しています。したがって、複数の接続されたコンポーネントを持つグラフの大文字と小文字を処理するようにBFSアルゴリズムを変更しない限り、このアルゴリズムは接続されていないグラフ内のすべてのノードと円弧を検出しません。