SHARE
TWEET

Untitled

a guest Aug 25th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class DepthFirstSearchHelper<T>
  2.     {
  3.         private 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.  
  8.         public DepthFirstSearchHelper(Graph<T> graph, Vertex<T> rootVertex = null)
  9.         {
  10.             _graph = graph;
  11.             _root = rootVertex ?? graph.Vertices.First();
  12.         }
  13.  
  14.         public List<T> Search()
  15.         {
  16.             _discovered.Clear();
  17.             _verticesColor.Clear();
  18.  
  19.             // mark all vertices white
  20.             foreach (var v in _graph.Vertices)
  21.             {
  22.                 _verticesColor[v] = VertexColor.White;
  23.             }
  24.  
  25.             // visit the root
  26.             Visit(_root);
  27.  
  28.             // check the adjacent edges now
  29.             foreach (var v in _root.Edges)
  30.             {
  31.                 if (_verticesColor[v] == VertexColor.White)
  32.                 {
  33.                     Visit(v);
  34.                 }
  35.             }
  36.             while (_verticesColor.Values.Contains(VertexColor.White))
  37.             {
  38.                 _root = _verticesColor.FirstOrDefault(x => x.Value == VertexColor.White).Key;
  39.                 Visit(_root);
  40.             }
  41.             return _discovered;
  42.         }
  43.  
  44.         private void Visit(Vertex<T> vertex)
  45.         {
  46.             _verticesColor[vertex] = VertexColor.Gray;
  47.             _discovered.Add(vertex.Value);
  48.  
  49.             foreach (var v in vertex.Edges)
  50.             {
  51.                 if (_verticesColor[v] == VertexColor.White)
  52.                 {
  53.                     Visit(v);
  54.                 }
  55.             }
  56.             _verticesColor[vertex] = VertexColor.Black;
  57.         }
  58.     }
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