BFSでグラフの最大深度を取得する方法

Question

グラフでBFSアルゴリズムを使用するとき、グラフの最大深度を取得しようとします。

しかし、このアルゴリズムでは、私の増分をどこに置くか、私は知りませんが：

FUNCTION BFS(G,s) 
     BEGIN 
      FOR any vertex v of G 
      DO Mark[v] ← False 
      END FOR Mark[s] ← True 
     F ← Empty Queue 
     enqueue(s,F) 
      WHILE F is not empty 
      DO v ← dequeue(F) 
       FOR any vertex w neighbor of v 
       DO 
        IF Mark[w] = False THEN 
        Mark[w] ← True; 
        enqueue(w,F) 
        END IF 
       FOR END 
      WHILE END 

私はFOR END後に数字の増分を入れてみましたが、それは本当の最大深さよりも優れた数を与えますグラフの

誰でも助けてください。

ありがとうございます。

Answer 1

グラフ上でBFSを実行するとツリーが得られ、実際にはという深さのツリーが表示されます。 END FORの後にインクリメントを置くと、（コードに応じて）ツリーの深さよりも大きな数値が得られます。この場合、現在の頂点「v」のすべての近傍が訪問され（すべてが真と記されている）、これは頂点vが葉であることを意味しますが、インクリメントは依然として1だけ増加します。

ソリューション：V現在のために、まだ（偽としてマークされて）訪問されていない、あなたはまだ他の頂点に対して深さが増加していないワット少なくとも一つの隣接があるとき、あなたの増分だけ増やす必要があります同じレベル（根元から同じ距離にある頂点）でwとなります。だからあなたのコードには、あなたがコードのレベルを追跡して、いつ増やすべきかを知る必要があるということがあります。

この質問には既にツリーが必要なので、レベルを追跡するためにコードを更新する方法を教えてください。How to keep track of depth in breadth first search?を参照する必要があります。単に、各レベルの終わりにNULLをキューにプッシュすることです。ルート自体はlevel0にあるので、ルートにキューをプッシュした後、NULLも押してください。その後、NULLが発生するたびに、次のレベルのキューにNULLをプッシュし、キューの先頭がNULLでないかどうかをチェックして深さを1つ増やし、それ以外の場合は中断します。私の友人と

FUNCTION BFS(G,s) 
    BEGIN 
     FOR any vertex v of G DO 
      Mark[v] ← False 
     END FOR 
     Mark[s] ← True 
     F ← Empty Queue 
     depth=0 
     enqueue(s,F), enqueue(NULL,F) // this is the level 0 
     WHILE F is not empty DO  
     v ← dequeue(F) 
     IF v=NULL THEN 
      enqueue(NULL,F) 
      IF(F.peek()==NULL) THEN 
       BREAK 
      ELSE 
       depth++ 
       Continue 
     FOR any vertex w neighbor of v DO 
      IF Mark[w] = False THEN 
       Mark[w] ← True; 
       enqueue(w,F) 
      END IF 
     FOR END 
     WHILE END 

Answer 2

我々は、この解決策を見つけた：

FUNCTION BFS(G,s) 
    BEGIN 
     FOR any vertex v of G 
     DO Mark[v] ← False 
     END FOR Mark[s] ← True 
    F ← Empty Queue 
    DIST [] ← Empty Tab 
    COUNTER = 0 
    enqueue(s,F) 
     WHILE F is not empty 
     DO v ← dequeue(F) 
      DIST[v] ← 0 
      FOR any vertex w neighbor of v 
      DO 
       IF Mark[w] = False THEN 
       Mark[w] ← True; 
       enqueue(w,F) 
       DIST[w] ← DIST[v] + 1 
        IF [COUNTER < DIST[w]] THEN 
        COUNTER = DIST[w]; 
        END IF 
       END IF 
      FOR END 
     WHILE END 
    RETURN (COUNTER); 
END FUNCTION 

previsouly私は間違ったものを掲載するので、私は、午前3時36分でAbdulhakeem 4月26日のコメントの後、この答えをeditied。