Rubyで深さ優先探索(DFS)と幅優先探索(BFS)

グラフ操作の基本、深さ優先探索(DFS: Depth First Search)と幅優先探索(BFS: Breadth First Search)のアルゴリズムをRubyで書く。

◆ DFS

	# 0
	# |
	# +-------+
	# | |
	# +-1-+ +-4-+
	# | | | |
	# 2 3 5 6
	class Node
	attr_reader :name, :children
	def initialize(name, *children)
	@name = name
	@children = children
	@visited = false
	end
	def visit
	puts @name
	@visited = true
	end
	def visited?
	@visited
	end
	end
	# 深さ優先探索 (DFS)
	def dfs_search(node)
	node.visit
	node.children.each do |child|
	dfs_search(child) unless child.visited?
	end
	end
	# ノードの作成
	node3 = Node.new(3)
	node4 = Node.new(4)
	node5 = Node.new(5)
	node6 = Node.new(6)
	node1 = Node.new(1, node3, node4)
	node2 = Node.new(2, node5, node6)
	node0 = Node.new(0, node1, node2)
	# 探索の実行
	dfs_search(node0)

view raw dfs.rb hosted with ❤ by GitHub

◆ BFS

	# 0
	# |
	# +-------+
	# | |
	# +-1-+ +-2-+
	# | | | |
	# 3 4 5 6
	class Node
	attr_reader :name, :children
	def initialize(name, *children)
	@name = name
	@children = children
	@visited = false
	end
	def visit
	puts @name
	@visited = true
	end
	def visited?
	@visited
	end
	end
	# 幅優先探索 (BFS)
	def bfs_search(root)
	queue = [root]
	root.visit
	until queue.empty?
	node = queue.shift
	node.children.each do |child|
	next if child.visited?
	child.visit
	queue << child
	end
	end
	end
	# ノードの作成
	node3 = Node.new(3)
	node4 = Node.new(4)
	node5 = Node.new(5)
	node6 = Node.new(6)
	node1 = Node.new(1, node3, node4)
	node2 = Node.new(2, node5, node6)
	node0 = Node.new(0, node1, node2)
	# 探索の実行
	bfs_search(node0)

view raw bfs.rb hosted with ❤ by GitHub