这里突出搜索算法，包括图上的，和搜索空间上的。还有一些规划算法。

树的遍历

很多搜索问题可以转化为树，二叉树是最基本的情况。

# 二叉树节点定义
class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val, left = nil, right = nil)
    @val = val
    @left = left
    @right = right
  end
end

# 二叉树的遍历（DFS）前序遍历（根 → 左 → 右）

# 递归版本
def preorder_recursive(root, res = [])
  return res if root.nil?
  res << root.val
  preorder_recursive(root.left, res)
  preorder_recursive(root.right, res)
  res
end

# 非递归（栈）版本
def preorder_iterative(root)
  return [] if root.nil?
  res = []
  stack = [root]
  while !stack.empty?
    node = stack.pop
    res << node.val
    # 先右后左入栈，保证出栈时左先遍历
    stack << node.right if node.right
    stack << node.left if node.left
  end
  res
end

# 测试二叉树遍历
root = TreeNode.new(1)
root.right = TreeNode.new(2)
root.right.left = TreeNode.new(3)

puts "前序递归: #{preorder_recursive(root)}"   # [1, 2, 3]
puts "前序非递归: #{preorder_iterative(root)}" # [1, 2, 3]

图的遍历

深度优先遍历

广度优先遍历

在树的基础上，有环。

# 图的遍历（DFS）

# 图的表示：邻接表（哈希，key 为节点，value 为相邻节点数组）
# 示例无向图
graph = {
  0 => [1, 2],
  1 => [0, 3, 4],
  2 => [0, 5],
  3 => [1],
  4 => [1, 5],
  5 => [2, 4]
}

# 递归 DFS
def dfs_recursive(graph, start, visited = Set.new, result = [])
  return result if start.nil?
  visited.add(start)
  result << start
  # 遍历邻居
  graph[start].each do |neighbor|
    unless visited.include?(neighbor)
      dfs_recursive(graph, neighbor, visited, result)
    end
  end
  result
end

# 非递归 DFS（栈实现）
def dfs_iterative(graph, start)
  return [] if start.nil?
  visited = Set.new
  stack = [start]
  result = []
  while !stack.empty?
    node = stack.pop
    next if visited.include?(node)
    visited.add(node)
    result << node
    # 逆序入栈，保证遍历顺序与递归一致（可选）
    graph[node].reverse_each do |neighbor|
      stack.push(neighbor) unless visited.include?(neighbor)
    end
  end
  result
end

# 图的广度优先遍历

# TODO

# 测试图遍历
require 'set'
puts "图递归 DFS: #{dfs_recursive(graph, 0)}"   # [0, 1, 3, 4, 5, 2]
puts "图非递归 DFS: #{dfs_iterative(graph, 0)}" # [0, 1, 3, 4, 5, 2]

线性规划

自行实现比较麻烦，建议调库。