SHARE
TWEET

Untitled

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