Schreiben Sie eine DFS mit iterativer Vertiefung ohne Rekursion

Also derzeit habe ich ein DFS mit den folgenden pseudocode

procedure DFS(Graph,source):
      create a stack S
      push source onto S
      mark source
      while S is not empty:
          pop an item from S into v
          for each edge e incident on v in Graph:
              let w be the other end of e
              if w is not marked:
                 mark w
                 push w onto S

Wie kann ich ändern, diese Funktion zu übernehmen, eine Dritte argument, das schränkt die Tiefe der Suche?

  • Es ist obligatorisch für den iterativen Weg? Es könnte so einfach sein mit Rekursion...
  • Es ist nicht ganz korrekt DFS-Algorithmus. Es besucht alle Nachfolger von vertex-und erst dann geht tiefer. Sollte es tiefer gehen zuerst, dann backtrack zu besuchen, die anderen untergeordneten Knoten.
InformationsquelleAutor Jonathan | 2011-09-21
  1. 2

    Lassen Knoten eine Struktur, die für jeden Knoten des Graphen, fügen Sie ein Feld namens Ebene und dann:

    procedure DFS(Graph,source, depth):
  create a stack S
  source.level = 0
  push source onto S
  mark source
  while S is not empty:
      pop an item from S into v
      if v.level > depth
        continue

      for each edge e incident on v in Graph:
          let w be the other end of e
          if w is not marked:
             mark w
             w.level = v.level + 1
             push w onto S
    • Schieben alle Nachbarn in den stack würde ein BFS-weil Sie am Ende der Suche bei den Nachbarn, bevor die Kinder.
    • Nop. Der entscheidende Punkt hier ist die Daten-Struktur, wenn Sie eine Warteschlange, dann bekommst du eine BFS, mit einem Stapel erhalten Sie einen DFS.
    • Ich denke, es gibt einige problem bei der obigen Lösung. Sie können pop ein Element von S in V sofort
    • Ich weiß, es scheint wie Python oder einer anderen Sprache, aber es ist pseudo-code: pop an item from S into v kann übersetzt werden in viele Anleitungen.
    InformationsquelleAutor rendon
Schreibe einen Kommentar