1

したがって、現在、次の擬似コードを含むDFSがあります

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

検索の深さを制限する 3 番目の引数を受け入れるようにこの関数を変更するにはどうすればよいですか?

4

2 に答える 2

2

Nodeをグラフの各ノードの構造とし、 levelというフィールドを追加してから、次のようにします。

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
于 2011-09-21T03:11:50.257 に答える