breadth-first-traverse

bread_first_traverse.py

import queue


class Node:
    def __init__(self, name):
        self._name = name
        self._children = []
        self.visited = False

    @property
    def children(self):
        return self._children

    @property
    def name(self):
        return self._name

    def addChild(self, child):
        self._children.append(child)

    def traverse(self):
        q = queue.Queue()
        q.put(self)
        while not q.empty():
            node = q.get()
            yield node
            for child in node.children:
                q.put(child)

def makeFive():
    ret = Node(0)
    a = Node(1)
    b = Node(2)
    c = Node(3)
    d = Node(4)
    a.addChild(c)
    b.addChild(d)
    ret.addChild(a)
    ret.addChild(b)
    return ret


def makeTwelve():
    nodes = [Node(i) for i in range(12)]
    nodes[0].addChild(nodes[1])
    nodes[0].addChild(nodes[2])
    nodes[0].addChild(nodes[3])
    nodes[1].addChild(nodes[4])
    nodes[1].addChild(nodes[5])
    nodes[3].addChild(nodes[6])
    nodes[3].addChild(nodes[7])
    nodes[4].addChild(nodes[8])
    nodes[4].addChild(nodes[9])
    nodes[6].addChild(nodes[10])
    nodes[6].addChild(nodes[11])
    return nodes[0]


def listify(node):
    return [n.name for n in node.traverse()]


if __name__ == '__main__':
    assert listify(makeFive()) == list(range(5))
    assert listify(makeTwelve()) == list(range(12))