RubyでDFS(深さ優先探索)の再帰呼び出しを実装

###入力：
今回は隣接行列表現で入力を与えます

例）

init.txt

0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 1 1 0
0 1 0 0 0 0 1 0 0 1
1 0 1 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0
0 0 1 0 1 0 0 0 0 0

###コード

dfs.rb

@V # 頂点数
@v = []
@matrix = []
@pre_cnt = 0 # pre配列のカウンタ
@pre_array = [] # pre配列
@st_array = [] # st配列

# 行列をファイルから入力
def init
    File.open(ARGV[0]) do |f|
        puts "入力 : "
        f.each_line do |line|
            list = []
            list = line.split(' ')

            row = []
            list.each do |val|
                row << val.to_i
            end
            p row
            @matrix << row
        end
    end

    @V = @matrix.size
end

def output
    # 調整
    graph_num = 0
    @st_array.each_with_index do |st, i|
        if st == nil
            @st_array[i] = i
            graph_num += 1
        end
    end

    print "\nindex   :  "
    @matrix.size.times do |i|
        print "#{i}  "
    end
    puts "\npre配列 : #{@pre_array}"
    puts "st配列  : #{@st_array}"
    puts "グラフ数 : #{graph_num}"
end


def DFS(i)
    @v[i] = 1;

    @V.times do |j|
        if (@matrix[i][j] == 1 && @v[j] == 0)
            puts "#{i} -> #{j}"

            #　pre配列を作る
            if @pre_array[i] == nil
                @pre_array[i] = @pre_cnt
                @pre_cnt += 1
            end

            if @pre_array[j] == nil
                @pre_array[j] = @pre_cnt
                @pre_cnt += 1
            end

            # st配列を作る
            @st_array[j] = i

            # 再帰呼び出し
            DFS(j)
        end
    end

end

def main
    init # 入力
    puts "\n頂点数 : #{@V}"

    @V.times do |i|
        @v[i] = 0
    end

    #/* -- 探索開始 -- */
    @V.times do |i|
        if @v[i] != 1
            DFS(i)
        end
    end

    output # 出力
end

if __FILE__ == $0
    main
end

###出力:

入力 :
[0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0]

頂点数 : 10
0 -> 5
5 -> 2
2 -> 6
6 -> 4
4 -> 1
4 -> 9
3 -> 7
7 -> 8

index  :  0  1  2  3  4  5  6  7  8  9
pre配列 : [0, 5, 2, 7, 4, 1, 3, 8, 9, 6]
st配列  : [0, 4, 5, 3, 6, 0, 2, 3, 7, 4]
グラフ数 : 2