Was ist der Unterschied zwischen der Breite zum ersten mal auf der Suche und level-order-traversal?

Ich brauche keinen code, nur eine Erklärung. Mein lehrbuch sagt

Ebene Reihenfolge: jeder Knoten auf Stufe i bearbeitet wird, bevor alle Knoten auf Ebene i+1

Mein Verständnis von der Breite zum ersten mal auf der Suche ist, dass Sie erkunden Knoten, der am nächsten an der Wurzel der ersten, beginnend von der linken? Wie ist das anders? Ist das eine Quadrat-und Rechteck-Art von situation?

  • Afaik gibt es keinen Unterschied; Sie können die "Breite-zuerst" - und "level-order" Synonym verwendet.
  • ^Dies. Jeder scheint, Sie zu definieren separat, sondern Sie buchstäblich das gleiche tun.
InformationsquelleAutor munchschair | 2014-05-10
  1. 18

    Für eine 'richtige' Struktur (siehe unten), es ist das gleiche, zumindest von den meisten Definitionen. Wie Wikipedia, zum Beispiel:

    Breadth-first

    Siehe auch: Breadth-first-search

    Bäume können auch befahren werden, die in Ebene -, um, ...

    ... zuerst der Breite (level-order), traversal ...

    Gut, zumindest die level-order-traversal ist das gleiche wie Breite-zuerst traversal. Es gibt viele Gründe, um die traverse etwas, es nicht nur zu suchen, als zuerst der Breite Suche scheint zu implizieren, obwohl viele (oder die meisten) nicht diese Unterscheidung machen, und verwenden Sie die Begriffe Synonym.

    Die einzige Zeit, die ich persönlich wirklich "level-order-traversal" ist, wenn man über in-, post - und pre-order traversals, einfach zu Folgen Sie den gleichen "...-order-traversal" - format.

    Für ein Allgemeines Diagramm ist, das Konzept einer 'Ebene' kann nicht wohlgeformt ist (obwohl Sie könnte nur die Definition der (kürzeste) Abstand von der source-Knoten, nehme ich an), also ein level-order-traversal eventuell nicht gut definiert, aber eine Breite-zuerst-Suche macht immer noch Sinn.

    Erwähnte ich einen "richtigen" Baum oben (das ist eine völlig aus sub-Klassifikation, im Fall Sie sich Wundern) - dies bedeutet einfach "level" definiert, wie man erwarten würde - jede Kante erhöht sich der level um eins. Jedoch, man kann in der Lage sein zu spielen, um mit der definition von "Niveau" ein bisschen (obwohl dies kann nicht überall akzeptiert), im wesentlichen so dass Kanten zu springen über die Ebenen (oder auch Kanten zwischen Knoten auf der gleichen Ebene). Zum Beispiel:

    level
  1          1
            /\
  2        /  3
          /  /
  3      2   4

    Also die level-order-traversal wäre 1, 3, 2, 4,

    während die Breite-zuerst-Traversierung wäre 1, 2, 3, 4.

    • Können Bäume sogar Ebenen in dieser Art und Weise? Ich habe nie gesehen, dass vor.
    • Ich habe nicht entweder, ich bin nur für die Buchhaltung Möglichkeit. Wenn "level" hat eine Bedeutung in den Daten, das entspricht nicht der Bedeutung von "Niveau" in den Bäumen, könnte man (etwas verwirrend) level-order-traversal, um zu bedeuten, dass die Reihenfolge der Traversierung.
    • Ich denke, das wäre eine "Last-order" - Traversierung, welche würden Sie bekommen durch die Verwendung einer priority-queue anstelle einer FIFO-Warteschlange in der Umsetzung der traverse (z.B. Dijkstra-Algorithmus). Das ist eindeutig sinnvoll ist, auch im Falle eines Allgemeinen Graphen, und ist sogar nützlich. Ich erinnere mich nicht, das Gehör der Satz "Gewicht-order traversal" vor, aber das kann meine verschlechtert Speicher; Google war nett genug, um zu finden eine Anzahl von Verwendungen der Satz, einschließlich papl.cs.brown.edu/2013/...
    InformationsquelleAutor Dukeling
  2. 0

    verwenden wir die Ebene um traversal für Bäume, denn Bäume gibt es keinen Zyklus und sobald ein Knoten besucht wird, ist es nicht gonna wieder besuchen
    aber in Graphen, dessen ist nicht so.
    Graph zyklisch sein als gut
    und wenn ein graph ist zyklisch, da pro level um, wenn ein Knoten besucht wird, die es nicht überprüfen, es besucht oder nicht, und wieder wird es Durchlaufen die gleichen Knoten unendlich oft. und das Programm wird weiterhin Durchlaufen, weil der Zyklus.
    So verwenden wir BFS oder DFS im Fall von graph.

    InformationsquelleAutor SUMIT LOHAN
Schreibe einen Kommentar