时间戳

首页 > 解决方案 > 堆栈级别太深 (SystemStackError) DFS

ruby - 堆栈级别太深 (SystemStackError) DFS

问题描述

我stack level too deep在执行DFS 算法以查找最大组件时遇到问题。问题是我正在将 map(.osm) 文件转换为图形。我想找到最大的组件。但是，使用小地图（缩放更大）它可以工作，但是使用更大的图表它会给我以上状态错误，你能帮我吗？这是导致问题的我的 DFS 代码：

def dfsFunction (vertex)
    @dfs[vertex] = true
    @component[@componentIndex] << vertex
    adjectenVertices = []
    @edges.each do |edge|
        if edge.v1.id == vertex.id
            adjectenVertices << edge.v2
        elsif edge.v2.id == vertex.id
            adjectenVertices << edge.v1
        end
    end
    adjectenVertices.each_with_index do |vertex|
        if @dfs[vertex] == false
            dfsFunction(vertex)
        end
    end
end




@dfs = {}
    @vertices.each do |id,vertex|
        @dfs[vertex] = false
    end
    @component = {}
    @componentIndex = -1
    @dfs.each do |vertex, boolean|
        if @dfs[vertex] == false
            @componentIndex = @componentIndex +1
            @component[@componentIndex] = []
            dfsFunction(vertex)
        end
    end

标签： rubygraph

解决方案

MRI 默认关闭尾递归优化。但有人可能会打开它：

RubyVM::InstructionSequence.compile_option = {
 tailcall_optimization: true,
 trace_instruction: false
}

此外，代码本身必须使用尾递归，如：

  def test(v)
    return unless v > 0
    p v
    test(v-1) 
  end

代替：

def test(v)
  test(v-1) if v > 0
  p v
end

推荐阅读