グラフが連結しているか判定する

幅優先探索(BFS)を用いて、グラフが連結しているか判定します。考え方は、次の通りです。

任意のグラフに対してBFSを行い、全ての頂点を訪問していた場合に、連結していると判定します。

実装

function isconnect(g)
    nexts = [1]
    seen = fill(false, length(g))
    seen[1] = true

    while !isempty(nexts)
        target_vertex = popfirst!(nexts)

        for vertex ∈ g[target_vertex]
            if seen[vertex]
                continue
            end

            push!(nexts, vertex)
            seen[vertex] = true
        end
    end

    return all(x -> x, seen)
end

g1 = [[2], [1, 3], [2]]

@show isconnect(g1)

g2 = [[], [1, 3], [2]]

@show isconnect(g2)

結果

yuu@penguin:~/src/jelly/0410$ julia sample.jl 
isconnect(g1) = true
isconnect(g2) = false