Breadth-first und depth-first-search-algorithmen in einem 5x5-raster von zahlen

Breite-zuerst-Suche bedeutet im wesentlichen: alle besuchen den übergeordneten Knoten, dann besuchen alle Kinder Knoten.

Während Tiefe-zuerst-Suche bedeutet: besuchen alle Kinder-Knoten zunächst, bis Sie Ihre Reichweite, einen Blatt-Knoten (Knoten ohne Kinder), dann besuchen Sie den nächsten übergeordneten Knoten und alle Kinder-Knoten und halten Sie auf, bis Sie besucht alle Knoten.

Hier haben Sie Bild (entnommen aus Wikipedia) zeigt, dass die Bestellung (durch einen Baum dargestellt), in der die Knoten besucht werden, die in einem Breite-zuerst-Suche:

Hier haben Sie das entsprechende Bild für eine Tiefe-zuerst-Suche:

Den pseudocode für

Breite-Zuerst-Suche:

def BFS(G,v):

    create a queue Q
    enqueue v onto Q
    mark v

    while Q is not empty:
      t = Q.dequeue()

      if t is what we are looking for:
          return t

      for all edges e in G.incidentEdges(t) do:
         o = G.opposite(t, e)

     if o is not marked:
          mark o
          enqueue o onto Q

Im wesentlichen erstellen Sie eine Warteschlange und dem hinzufügen aller Knoten, die in...
Erinnere mich an eine Warteschlange ist first-in-first-out - Datenstruktur.

Depth-First Suche:

def DFS(G, v):
    label v as explored

    for all edges e in G.incidentEdges(v) do:

      if edge e is unexplored then:

          w = G.opposite(v, e)

          if vertex w is unexplored then:

              label e as a discovery edge
              recursively call DFS(G, w)
      else 
         label e as a back edge

Nun, für diesen einen, Sie sind ziemlich viel für eine Einstellung erkundet Flagge, wenn Sie erforscht haben, alle von Ihnen, dann haben Sie getan, depth-first-Suche um.

InformationsquelleAutor Kevin