# 幅優先探索→深さ優先探索でした＞＜

バックトラックとかしなくていいので、結構簡単にできた。

```# -*- coding: utf-8 -*-
require 'pp'

class Graph
def initialize(edges)
@edges = edges
@nodes = Hash.new{|h,k| h[k] = []}
end

@edges.push edge unless @edges.index(edge)
end

if @edges.index(u).nil?
@edges.push u
elsif @edges.index(v).nil?
@edges.push v
end

unless @nodes[u].index(v)
@nodes[u].push v
end
end

def breadth_first_search(start, has_approached = [], indent = 0)
puts " " * indent + start
has_approached.push start
@nodes[start].each{|node|
unless has_approached.include?(node)
end
}
end
end

g = Graph.new([1, "2", "3"])

pp g

```

```/tmp% ruby hash_graph.rb
#<Graph:0x8898c
@edges=[1, "2", "3", "8", "1", "6", "9"],
@nodes={"1"=>["5", "6", "3"], "2"=>["6", "9"], "3"=>["2"]}>
1
5
6
3
2
9
```

## 追記

### 再帰を使わない深さ優先探索の実装

```# -*- coding: utf-8 -*-
require 'pp'

class Graph
def initialize(edges)
@edges = edges
@nodes = Hash.new{|h,k| h[k] = []}
end

@edges.push edge unless @edges.index(edge)
end

if @edges.index(u).nil?
@edges.push u
elsif @edges.index(v).nil?
@edges.push v
end

unless @nodes[u].index(v)
@nodes[u].push v
end
end

def dfs(s)
stack = []
stack.push s
explored = []
while(!stack.empty?)
u = stack.shift
if explored.include?(u) == false
explored.push u
@nodes[u].each{|v|
stack.unshift v
}
end
end
return explored
end

end

g = Graph.new([1, "2", "3"])

```/tmp% ruby hash_graph.rb