Artificial intelligence‎ > ‎Graph‎ > ‎

Breadth-first search

What I want from each and every one of you is a hard-target search of every gas station, residence, warehouse, farmhouse, henhouse, outhouse and doghouse in that area.

Breadth-first search (BFS) is a algorithm for traversing a graph structure. It visits all nodes one step away from the start node, then two steps away from the start node and so on until a goal node is found or there are no more links to follow.

Algorithm
    Enqueue the start node.
    dequeue a node until queue is empty
        If this is the element we need quit and return the result.
        Explore all links to node and enqueue the nodes that we have not yet explored
    When the queue is empty we are done and no result was found.

Pseudocode
function BFS(g, v)
    queue Q
    set V

    Q.push(v)
    V.push(v)

    while !Q.empty() do
        t = Q.pop()

        foreach each edge e in v do
            u = e.tonode
            if u not in V then
                V.push(u)
                q.push(u)
            end
        end
    end
end

Comments