🦔

N頂点M辺を受け取る無向グラフの表現

2024/04/05に公開

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