如何使用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 

我試圖把一個數的遞增年底之後，但它比真正的最大深度出衆的數的圖。

請任何人都可以幫助我。

謝謝。

Answer 1

在圖表上運行BFS會爲您提供一棵樹，實際上您想要的是樹的深度。在END FOR之後加一個增量值絕對會給你一個大於樹的深度的數字（取決於你的代碼）。設想這種情況：訪問當前頂點'v'的所有鄰居（所有這些鄰居都標記爲真），這意味着頂點v是葉但您的增量仍然會增加1，這是不正確的。

解決方案：您的增量應該只增加當電流v至少有一個鄰居W¯¯還未被訪問（標記爲假），你還沒有增加的深度任何其他頂點與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 

我Abdulhakeem 4月26日的3:36的評論後editied這個答案，因爲我previsouly貼錯了。