广度优先算法实现

Question

我正在尝试实现一个 "Breadth-First" 算法作为我在书中看到的算法的变体。

我的问题是算法没有将每个节点的元素添加到队列中。

例如，如果我在 "search()" 函数中搜索名称 'mariela' 下的 "black lab"，我将得到正确的输出："simon is a black lab"

但是，我应该能够在 "walter" 中查找 "black lab"，它连接到 "mariela"，它连接到 "simon"，谁是“黑色实验室”。这不起作用。

我是不是在实现这个算法时犯了一个新手错误，或者我的图表设置有误？

一如既往，any/all 非常感谢您的帮助！

from collections import deque


# TEST GRAPH -------------
graph = {}
graph['walter'] = ['luci', 'kaiser', 'andrea', 'mariela']
graph['andrea'] = ['echo', 'dante', 'walter', 'mariela']
graph['mariela'] = ['ginger', 'simon', 'walter', 'andrea']
graph['kaiser'] = 'german shepherd'
graph['luci'] = 'black cat'
graph['echo'] = 'pitbull'
graph['dante'] = 'pitbull'
graph['ginger'] = 'orange cat'
graph['simon'] = 'black lab'



def condition_met(name):
    if graph[name] == 'black lab':
        return name


def search(name):
    search_queue = deque()
    search_queue += graph[name]             # add all elements of    "name" to queue
    searchedAlready = []                    # holding array for people    already searched through

while search_queue:                     # while queue not empty...
    person = search_queue.popleft()     # pull 1st person from queue
    if person not in searchedAlready:   # if person hasn't been searched through yet...
        if condition_met(person):
            print person + ' is a black labrador'
            return True
    else:
        search_queue += graph[person]
        searchedAlready.append(person)
return False


 search('walter')
#search('mariela')

Answer 1

您在实施中有很多问题 - Python 和算法方面。

重写为：

# @param graph  graph to search
# @param start  the node to start at
# @param value  the value to search for
def search(graph, start, value):
  explored = []
  queue = [start]
  while len(queue) > 0:
    # next node to explore
    node = queue.pop()
    # only explore if not already explored
    if node not in explored:
      # node found, search complete
      if node == value:
        return True
      # add children of node to queue
      else:
        explored.append(node)
        queue.extend(graph[node]) # extend is faster than concat (+=)
  return False


graph = {}
graph['walter'] = ['luci', 'kaiser', 'andrea', 'mariela']
graph['andrea'] = ['echo', 'dante', 'walter', 'mariela']
graph['mariela'] = ['ginger', 'simon', 'walter', 'andrea']

# children should be a list
graph['kaiser'] = ['german shepherd'] 
graph['luci'] = ['black cat']
graph['echo'] = ['pitbull']
graph['dante'] = ['pitbull']
graph['ginger'] = ['orange cat']
graph['simon'] = ['black lab']

print search(graph, 'mariela', 'walter')

这是一个演示 https://repl.it/IkRA/0

广度优先算法实现

Breadth-first algorithm implementation

algorithm

breadth-first-search