BFS – Breadth-first search – Python implementation

from queue import Queue

def BFS(graph,root,target):
    q = Queue()
    checked = []
    q.enqueue(root)
    path = 0
    while not q.isEmpty():
        v = q.dequeue()
        if v == target:
           return True
        elif v not in checked:
            for edge in graph[v]:
                if v not in checked:
                    q.enqueue(edge)
            checked.append(v)
    return False
graph = {1: [2, 3],
         2: [1, 4, 5, 6],
         3: [1, 4],
         4: [2, 3, 5],
         5: [2, 4, 6],
         6: [2, 5]}

 

Advertisements

Tags: , ,

3 responses to “BFS – Breadth-first search – Python implementation”

  1. Peter says :

    I’m a total newbie with Python, but it looks like you didn’t use path. Also, wouldn’t it be useful to send functions (or lambdas) instead? The following seems to work:

    def BFS(start,child_fn,goal_fn,keepPath=False):
    ”’Breadth-first search with option to keep the winning search path”’
    q = Queue()
    checked = []
    q.put([start] if keepPath else start)
    while not q.empty():
    v = q.get()
    v_val = v[0] if keepPath else v
    if goal_fn(v_val):
    return (v)
    elif v_val not in checked:
    for edge in child_fn(v_val):
    if v_val not in checked:
    q.put([edge]+v if keepPath else edge)
    checked.append(v_val)
    return False

    graph = {1: [2, 3],
    2: [1, 4, 6],
    3: [1, 4],
    4: [2, 3, 5],
    5: [2, 4, 6],
    6: [2, 5, 9]}

    BFS(1, lambda x: graph[x], lambda x: x*x == 81)

    Out[102]: [9, 6, 2, 1]

  2. Peter says :

    Oops sorry no indentation shown.

  3. badc0re says :

    Actually idk the performance of lambda, is it faster or not. And yeah in my example i only traverse through the whole graph.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: