Breadth-First search lazy vertex iterator

Topics: algorithm, graph
Nov 26, 2010 at 9: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 12: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>();
            yield return source;
            while (queue.Count != 0) {
                var v = queue.Dequeue();
                foreach (var w in g.GetAdjacentVertices(v)) {
                    if(!marked.Contains(w)) {
                        yield return w;