🦔
N頂点M辺を受け取る無向グラフの表現
N頂点M辺を受け取る無向グラフを表現する方法を示します。
隣接リスト
入力
3 3
1 2
1 3
2 3
ソースコード
n, m = readline() |> split |> x -> parse.(Int, x)
g = [[] for _ ∈ 1:n]
for _ ∈ 1:m
a, b = readline() |> split |> x -> parse.(Int, x)
push!(g[a], b)
push!(g[b], a)
end
@show g
結果は、次の通りになります。
yuu@penguin:~/src/nyuwa/0405$ julia sample.jl
3 3
1 2
1 3
2 3
g = Vector{Any}[[2, 3], [1, 3], [1, 2]]
隣接行列
入力
3 3
1 2
1 3
2 3
ソースコード
n, m = readline() |> split |> x -> parse.(Int, x)
g = zeros(Int8, n, n)
for _ ∈ 1:m
a, b = readline() |> split |> x -> parse.(Int, x)
g[a, b] = 1
g[b, a] = 1
end
@show g
結果は、次の通りになります。
yuu@penguin:~/src/nyuwa/0405$ julia sample.jl
3 3
1 2
1 3
2 3
g = Int8[0 1 1; 1 0 1; 1 1 0]
Discussion