lib/math/discrete/graph/algorithms.rb
def depth_first_search(root: vertex_set.first)
    return {} if @vertex_map.empty?

    raise TypeError, 'root must be of the type Math::Discrete::Graph::Vertex' unless root.is_a? Vertex
    raise Graph::VertexNotFound, "could not find vertex with label=#{root.label}" unless vertex_labels.include? root.label


    search_stack = Containers::Stack.new [root]
    search_tree = { root.label => { distance: 0, parent: nil } }

    until search_stack.empty?
      vertex = search_stack.pop

      vertex.adjacent_vertices.each do |child|
        if search_tree[child.label].nil?
          search_tree[child.label] = {
            distance: search_tree[vertex.label][:distance] + 1,
            parent: vertex.label
          }

          search_stack.push child
        end
      end
    end

    search_tree
  end
# Depth-first search (DFS) is an algorithm for traversing a graph
# It starts at the given root and explores as far as possible along each branch before backtracking.
# Read more:
# https://en.wikipedia.org/wiki/Depth-first_search
Depth-first search (DFS) is an algorithm for traversing a graph
It starts at the given root and explores as far as possible along each branch before backtracking.
Depth - first search ( DFS ) is an algorithm for traversing a graph It starts at the given root and explores as far as possible along each branch before backtracking .
def depth_first_search(root: vertex_set.first)
    return {} if @vertex_map.empty?
    raise TypeError, 'root must be of the type Math::Discrete::Graph::Vertex' unless root.is_a? Vertex
    raise Graph::VertexNotFound, "could not find vertex with label=#{root.label}" unless vertex_labels.include? root.label
    search_stack = Containers::Stack.new [root]
    search_tree = { root.label => { distance: 0, parent: nil } }
    until search_stack.empty?
      vertex = search_stack.pop
      vertex.adjacent_vertices.each do |child|
        if search_tree[child.label].nil?
          search_tree[child.label] = {
            distance: search_tree[vertex.label][:distance] + 1,
            parent: vertex.label
          }
          search_stack.push child
        end
      end
    end
    search_tree
  end
def depth_first_search ( root : vertex_set . first ) return { } if @vertex_map . empty? raise TypeError , 'root must be of the type Math::Discrete::Graph::Vertex' unless root . is_a? Vertex raise Graph :: VertexNotFound , "could not find vertex with label=#{root.label}" unless vertex_labels . include? root . label search_stack = Containers :: Stack . new [ root ] search_tree = { root . label => { distance : 0 , parent : nil } } until search_stack . empty? vertex = search_stack . pop vertex . adjacent_vertices . each do | child | if search_tree [ child . label ] . nil? search_tree [ child . label ] = { distance : search_tree [ vertex . label ] [ :distance ] + 1 , parent : vertex . label } search_stack . push child end end end search_tree end
Depth-first search (DFS) is an algorithm for traversing a graph
It starts at the given root and explores as far as possible along each branch before backtracking.
Depth - first search ( DFS ) is an algorithm for traversing a graph It starts at the given root and explores as far as possible along each branch before backtracking .
root
vertex_set
first