bfs_example


Breadth First Search in Python

A quick example using NetworkX to implement a basic graph algorithm.

Allen B. Downey

MIT License


In [1]:
# this line makes the code compatible with Python 2 and 3
from __future__ import print_function, division

# this line makes Jupyter show figures in the notebook
%matplotlib inline

In [2]:
from collections import deque

def bfs(G, start):
    """A simple version of BFS that just computes distances.
    
    G: Graph
    start: int start node
    
    returns: map from node to distance
    """
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()         
        for child in G.neighbors(node):
            if child not in dist:                    
                dist[child] = dist[node] + 1
                queue.append(child)
    return dist

In [3]:
from networkx import DiGraph

def bfs(G, start):
    """A simple version of BFS that computes distances and
        paths back to start.
    
    G: Graph
    start: int start node
    
    returns: (map from node to distance,
        DiGraph containing paths from each node back to start)
    """
    dist = {start: 0}
    tree = DiGraph()
    queue = deque([start])
    while queue:
        node = queue.popleft()         
        for child in G.neighbors(node):
            if child not in dist:                    
                dist[child] = dist[node] + 1
                tree.add_edge(child, node) 
                queue.append(child)
    return dist, tree

In [4]:
from numpy.random import random

def flip(p):
    return random() < p

In [5]:
def random_pairs(nodes, p):
    """Generate random pairs of nodes."""
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i<j and flip(p):
                yield u, v

In [6]:
import networkx as nx

def make_random_graph(n, p):
    """Generate a random graph.
    
    n: number of nodes
    p: probability of an edge between any pair of nodes
    
    returns: Graph
    """
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(random_pairs(nodes, p))
    return G

In [7]:
random_graph = make_random_graph(10, 0.3)
len(random_graph.edges())


Out[7]:
12

In [8]:
import seaborn as sns
COLORS = sns.color_palette()

nx.draw_circular(random_graph, 
                 node_color=COLORS[2], 
                 node_size=1000, 
                 with_labels=True)



In [9]:
dist, tree = bfs(random_graph, 0)
dist


Out[9]:
{0: 0, 1: 3, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 1, 8: 2, 9: 1}

In [10]:
nx.draw_circular(tree, 
                 node_color=COLORS[2], 
                 node_size=1000, 
                 with_labels=True)



In [11]:
def fft(ys):
    N = len(ys)
    if N == 1:
        return ys
    
    He = fft(ys[::2])
    Ho = fft(ys[1::2])
    
    ns = np.arange(N)
    W = np.exp(-1j * PI2 * ns / N)
    
    return np.tile(He, 2) + W * np.tile(Ho, 2)

In [ ]: