Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class DepthFirstSearchHelper<T>
- {
- private Vertex<T> _root;
- private readonly List<T> _discovered = new List<T>();
- private readonly Dictionary<Vertex<T>, VertexColor> _verticesColor = new Dictionary<Vertex<T>, VertexColor>();
- private readonly Graph<T> _graph;
- public DepthFirstSearchHelper(Graph<T> graph, Vertex<T> rootVertex = null)
- {
- _graph = graph;
- _root = rootVertex ?? graph.Vertices.First();
- }
- public List<T> Search()
- {
- _discovered.Clear();
- _verticesColor.Clear();
- // mark all vertices white
- foreach (var v in _graph.Vertices)
- {
- _verticesColor[v] = VertexColor.White;
- }
- // visit the root
- Visit(_root);
- // check the adjacent edges now
- foreach (var v in _root.Edges)
- {
- if (_verticesColor[v] == VertexColor.White)
- {
- Visit(v);
- }
- }
- while (_verticesColor.Values.Contains(VertexColor.White))
- {
- _root = _verticesColor.FirstOrDefault(x => x.Value == VertexColor.White).Key;
- Visit(_root);
- }
- return _discovered;
- }
- private void Visit(Vertex<T> vertex)
- {
- _verticesColor[vertex] = VertexColor.Gray;
- _discovered.Add(vertex.Value);
- foreach (var v in vertex.Edges)
- {
- if (_verticesColor[v] == VertexColor.White)
- {
- Visit(v);
- }
- }
- _verticesColor[vertex] = VertexColor.Black;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement