Commit f440dfe

mo khan <mo@mokhan.ca>
2013-09-05 04:09:01
switch dfs to walk a graph not just a tree.
main
1 parent 40e98c3
Changed files (1)
spec
data_structures
depth_first_search_spec.rb
spec/data_structures/depth_first_search_spec.rb
@@ -3,23 +3,22 @@ require "ostruct"
 
 def dfs(node)
   stack = [node]
-  until(stack.empty?) do
+  until stack.empty? do
     top = stack.pop
     p top.name
-    stack.push(top.left) if top.left
-    stack.push(top.right) if top.right
+    top.children.reverse_each { |x| stack.push(x) }
   end
 end
 
 describe "dfs" do
   it "should visit each item" do
-    nailah = OpenStruct.new(:name => "nini", :left => nil, :right => nil)
-    adia = OpenStruct.new(:name => "adia", :left => nil, :right => nil)
-    allison = OpenStruct.new(:name => "alli", :left => adia, :right => nailah)
-    caius = OpenStruct.new(:name => "caius", :left => nil, :right => nil)
-    reeves = OpenStruct.new(:name => "reeves", :left => nil, :right => nil)
-    lisa = OpenStruct.new(:name => "lisa", :left => caius, :right => reeves)
-    sandi = OpenStruct.new(:name => "sandi", :left => allison, :right => lisa)
+    nailah = OpenStruct.new(:name => "nini", :children => [])
+    adia = OpenStruct.new(:name => "adia", :children => [])
+    allison = OpenStruct.new(:name => "alli", :children => [adia, nailah])
+    caius = OpenStruct.new(:name => "caius", :children => [])
+    reeves = OpenStruct.new(:name => "reeves", :children => [])
+    lisa = OpenStruct.new(:name => "lisa", :children => [caius, reeves])
+    sandi = OpenStruct.new(:name => "sandi", :children => [allison, lisa])
     dfs(sandi)
   end
 end