.. Breadth first search

幅優先探索
====================

::

  #!>>
  #!"someNode"から探索を始める、シンプルな線形時間のグラフ探索アルゴリズム。
  #!
  #!u, vはグラフの二つのノード。もしも"someNode"とuの間の距離が、"someNode"とvの
  #!距離よりも短ければ、vよりもuの方が先に探索される。
  #!
  #!もしもノードがはじめて探索されると、レベル属性("someNode"と
  #!そのノードの間の距離を示す)が設定される。
  #!<<
  
  #![SD breadth-first-search]
  bfs:BFS[a]
  /queue:FIFO
  someNode:Node
  node:Node
  adjList:List
  adj:Node


  bfs:queue.new
  bfs:someNode.setLevel(0)
  bfs:queue.insert(someNode)
  [c:loop while queue != ()]
    bfs:node=queue.remove()
    bfs:level=node.getLevel()
    bfs:adjList=node.getAdjacentNodes()
    [c:loop 0<=i<#adjList]
      bfs:adj=adjList.get(i)
      bfs:nodeLevel=adj.getLevel()
      [c:alt nodeLevelが未定義の場合]
        bfs:adj.setLevel(level+1)
        bfs:queue.insert(adj)
        --[else]
        bfs:何もしない
      [/c]
    [/c]
  [/c]
  bfs:queue.destroy()

.. image:: bfs.png

.. 
  #!>>
  #!A simple linear-time algorithm for exploring a graph, starting at "someNode". 
  #!
  #!Let u, v be two nodes of the graph. If the distance between "someNode" and u
  #!is less than the distance between "someNode" and v, then u will be encountered
  #!before v.
  #!
  #!When a node is encountered for the first time, its level attribute (denoting the
  #!distance between "someNode" and the node) is set.
  #!<<
  
  #![SD breadth-first-search]