Breadth-First search lazy vertex iterator

Topics: algorithm, graph
Nov 26, 2010 at 10:39 PM

Hi everybody ! Thanks for such a cool library.

I wondering if there is a way to represent Breadth-First search algorithm as vertex iterator, so i can pull vertices one-by-one in a lazy manner ?

Thank you.

Nov 30, 2010 at 1:54 AM

OK, i just reimplemented it (based on wikipedia pseudocode). Probably it's the easiest way

public static IEnumerable<TVertex> GetBreadthFirstIterator<TVertex, TEdge>(this BidirectionalGraph<TVertex, TEdge> g,
                                                                                   TVertex source)
            where TEdge : IEdge<TVertex>
        {
            var queue = new Queue<TVertex>();
            var marked = new HashSet<TVertex>();
            queue.Enqueue(source);
            marked.Add(source);
            yield return source;
            while (queue.Count != 0) {
                var v = queue.Dequeue();
                foreach (var w in g.GetAdjacentVertices(v)) {
                    if(!marked.Contains(w)) {
                        marked.Add(w);
                        yield return w;
                        queue.Enqueue(w);
                    }
                }
            }
        }