SHARE
TWEET

Untitled

a guest Aug 25th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.   class BreadthFirstSearchHelper<T>
  2.     {
  3.         private readonly Vertex<T> _root;
  4.         private readonly List<T> _discovered = new List<T>();
  5.         private readonly Dictionary<Vertex<T>, VertexColor> _verticesColor = new Dictionary<Vertex<T>, VertexColor>();
  6.         private readonly Graph<T> _graph;
  7.         private readonly Queue<Vertex<T>> _queue = new Queue<Vertex<T>>();
  8.  
  9.         public BreadthFirstSearchHelper(Graph<T> graph, Vertex<T> root = null)
  10.         {
  11.             _graph = graph;
  12.             _root = root ?? _graph.Vertices.First();
  13.         }
  14.  
  15.         public List<T> Search()
  16.         {
  17.             // mark all vertices as white
  18.             foreach (var vertex in _graph.Vertices)
  19.             {
  20.                 _verticesColor[vertex] = VertexColor.White;
  21.             }
  22.  
  23.             // mark the root as gray
  24.             _verticesColor[_root] = VertexColor.Gray;
  25.  
  26.             _queue.Enqueue(_root);
  27.             while (_queue.Any())
  28.             {
  29.                 var u = _queue.Peek();
  30.                 foreach (var v in u.Edges)
  31.                 {
  32.                     if (_verticesColor[v] == VertexColor.White)
  33.                     {
  34.                         _discovered.Add(v.Value);
  35.                         _queue.Enqueue(v);
  36.                     }
  37.                 }
  38.                 _queue.Dequeue();
  39.                 _verticesColor[u] = VertexColor.Black;
  40.             }
  41.  
  42.             return _discovered;
  43.         }
  44.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top