So erhalten Sie die maximale Tiefe eines Graphen mit BFS

Question

Wenn ich einen BFS-Algorithmus für ein Diagramm verwende, versuche ich die maximale Tiefe des Diagramms zu erhalten.

Aber ich weiß nicht, wo meine Inkrementierung in diesem Algorithmus setzen:

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 

ich versuchte, für eine Inkrementierung einer Zahl nach dem Ende zu setzen, aber es gibt eine Reihe überlegen, als die reale maximale Tiefe des Graphen.

Bitte kann mir jemand helfen.

Vielen Dank.

Answer 1

Das Ausführen von BFS auf einem Diagramm gibt Ihnen einen Baum und was Sie eigentlich wollen, ist die Tiefe des Baums. Wenn Sie nach dem END FOR eine Inkrementierung einfügen, erhalten Sie absolut eine Zahl, die größer als die Tiefe des Baumes ist (abhängig von Ihrem Code). Stellen Sie sich diesen Fall vor: Alle Nachbarn des aktuellen Eckpunkts 'v' werden besucht (alle als wahr markiert), dh der Eckpunkt v ist Blatt, aber Ihre Inkrementierung wird immer noch um eins erhöht, was nicht korrekt ist.

Lösung: Ihre Inkrementierung sollte nur erhöhen, wenn für Strom v gibt es mindestens ein Nachbar w, die noch nicht besucht (als falsch markiert) ist, und Sie erhöht noch nicht die Tiefe für einen anderen Eckpunkt auf der gleichen Ebene (Vertices in der gleichen Entfernung von der Wurzel 's) wie w. Also, was Sie in Ihrem Code fehlt, sollten Sie den Stand in Ihrem Code zu wissen, wann zu erhöhen.

Diese Frage wurde bereits nach einem Baum gestellt, also müssen Sie sich vielleicht How to keep track of depth in breadth first search? ansehen, damit Sie wissen, wie Sie Ihren Code aktualisieren, um den Überblick zu behalten. Einfach die Idee ist, am Ende jeder Ebene eine NULL in die Warteschlange zu schieben. Die Wurzel selbst ist auf Level0, also nachdem Sie root in die Warteschlange geschoben haben, drücken Sie auch einen NULL. Danach drücken Sie bei jedem Auftreten von NULL NULL auf die Warteschlange für die nächste Stufe und prüfen, ob der obere Teil der Queue nicht NULL ist, erhöhen Sie die Tiefe um eins und setzen Sie else break fort.

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

Mit meinem Freund fanden wir diese Lösung:

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 

ich editied diese Antwort nach dem Kommentar von Abdulhakeem 26. April um 3:36, weil previsouly gepostet ich die falsche.