BFS - Matlab implementation of Breadth first search algorithm.

Contents

Description

Compute breadth first search (BFS) distances, times, and tree for a graph and enumerates valid paths.

Syntax

   [d dt path pred] = bfs(A,u,target);

[d dt pred] = bfs(A,u) returns the distance d and the discover time dt for each vertex in the graph in a breadth first search starting from vertex u.

[...] = bfs(A,u,v) stops the BFS when it hits the vertex v.

Remarks:

Example

load_gaimc_graph('bfs_example.mat') % use the dfs example from Boost
d = bfs(A,1)

Acknowledgment

David F. Gleich Copyright, Stanford University, 2008-2009

See also

Ressembles: DFS, GAIMC/SCOMPONENTS.

Function implementation

function [d dt path pred] = bfs(A,u,target)

if ~exist('target','var'), target=0; end

if isstruct(A), rp=A.rp; ci=A.ci;
else [rp ci]=sparse_to_csr(A);
end

n=length(rp)-1;
d=-1*ones(n,1); dt=-1*ones(n,1); pred=zeros(1,n);
sq=zeros(n,1); sqt=0; sqh=0; % search queue and search queue tail/head

path = [];

% start bfs at u
sqt=sqt+1; sq(sqt)=u;
t=0;
d(u)=0; dt(u)=t; t=t+1; pred(u)=u;
while sqt-sqh>0
    sqh=sqh+1; v=sq(sqh); % pop v off the head of the queue
    for ri=rp(v):rp(v+1)-1
        w=ci(ri);
        if d(w)<0
            sqt=sqt+1; sq(sqt)=w;
            d(w)=d(v)+1; dt(w)=t; t=t+1; pred(w)=v;
            if w==target,
                return;
            end
        end
    end
end
end % end of bfs