Depth First Search

Posted by kev Tue, 27 Nov 2007 19:24:00 GMT

Because I hadn’t implemented DFS in Ruby before, and it’s just so damn easy.

Update: Phillip rightly pointed out in the comments that with the yield at the end, it’s actually post-order traversal, not depth first search per se.

class TreeNode
  attr_reader :name

  def initialize(name)
    @name = name
    @children = []
  end

  def add_node(node)
    @children << node
  end

  def each_depth_first
    @children.each do |child|
      child.each_depth_first do |c|
        yield c
      end
    end

    yield self
  end
end

# root  -  a  -  b
#   \       \ 
#    e - f   c  -  d
#     \
#      g

root = TreeNode.new("root")
root.add_node( a = TreeNode.new("a"))
a.add_node( b = TreeNode.new("b"))
a.add_node( c = TreeNode.new("c"))
c.add_node( d = TreeNode.new("d"))
root.add_node(e = TreeNode.new("e"))
e.add_node(f = TreeNode.new("f"))
e.add_node(g = TreeNode.new("g"))

root.each_depth_first do |child|
  puts child.name
end

# produces:
# b
# d
# c
# a
# f
# g
# e
# root

Posted in ,  | 3 comments

Comments

  1. Avatar Uzytkownik said about 3 hours later:

    > a = TreeNode.new(“a”) > root.add_node( a = TreeNode.new(“a”))

    I don’t think the first line is needed ;)

  2. Avatar Philip said about 5 hours later:

    Don’t mean to split hairs, but I think you meant ‘postorder’ search (traversal), not depth-first..

    Depth-first would output root, a,b,c,e,f,g (and would be equally as easy to implement, which was the gist of your post, I think)

  3. Avatar Kevin Clark said about 13 hours later:

    Phillip: Quite right. Long day. Sorry.

    Uzytkownik: Also true.

RSS feed for this post

Comments are disabled