MATLAB移民のためのJulia tips

MATLAB移民のためのJulia tips

何も考えずに速く計算できないのならば、何もやりたくない。

深さ優先探索(DFS)：グラフの連結成分

サンプル

どこにでも書いてある、DFSで連結成分を出してくるという操作のサンプル。
特にJuliaだから特殊ということはないはず。
枝の集合linksが与えられたときに、連結成分の頂点CCnodesを返す。

Stackでやる方法

function dfs_stack(nb,root)
    visited = Int64[]
    stack = push!(Int64[],root)
    while !isempty(stack)
        node = pop!(stack)
        if node in visited
            continue
        else
            push!(visited,node)
            append!(stack,filter(x->!(x in visited), nb[node]))
        end
    end
    return visited
end

links = [1 2; 2 3; 2 4; 4 1; 1 5; 4 5;3 4; 7 8; 8 9; 9 7; 4 8]
Ntot = maximum(links)
links = vcat(hcat(links[:,2],links[:,1]),links)
nb = [links[links[:,1].==lnode,2] for lnode = 1:Ntot]

CCnodes = dfs_stack(nb,1)
sort(CCnodes)

8-element Array{Int64,1}:
1
2
3
4
5
7
8
9

再帰でやる方法

function DFS(nb, root, visited=nothing) 
    if visited == nothing
        visited = Int64[]
    end

    if root in visited
        return
    end
    
    push!(visited,root)
    
    for vertex in filter(x->!(x in visited), nb[root])
        DFS(nb, vertex, visited)
    end
    return visited
end

links = [1 2; 2 3; 2 4; 4 1; 1 5; 4 5;3 4; 7 8; 8 9; 9 7; 4 8]
Ntot = maximum(links)
links = vcat(hcat(links[:,2],links[:,1]),links)
nb = [links[links[:,1].==lnode,2] for lnode = 1:Ntot]

CCnodes = DFS(nb,1,nothing)
sort(CCnodes)

結果は前と同じ。