有向グラフと無向グラフを隣接リスト構造で表現する

隣接リスト構造の作り方を示す。

有向グラフ

$$N頂点、M辺がありa_iとb_iからa_mとb_mの辺がaからbの向きで繋がっている場合の隣接リスト構造を作ってみます。$$

入力

4 4
1 2
2 3
2 4
3 4

実装

n, m = readline() |> split |> x -> parse.(Int, x)

graph = [[] for _ ∈ 1:n]

for _ ∈ 1:m
    a, b = readline() |> split |> x -> parse.(Int, x)

    push!(graph[a], b)
end

@show graph

結果

yuu@penguin:~/src/daikon/20240306$ julia graph.jl 
4 4
1 2
2 3
2 4
3 4
graph = Vector{Any}[[2], [3, 4], [4], []]

有向グラフ

$$N頂点、M辺がありa_iとb_iからa_mとb_mの辺が繋がっている場合の隣接リスト構造を作ってみます。$$

入力

4 4
1 2
2 3
2 4
3 4

実装

n, m = readline() |> split |> x -> parse.(Int, x)

graph = [[] for _ ∈ 1:n]

for _ ∈ 1:m
    a, b = readline() |> split |> x -> parse.(Int, x)

    push!(graph[a], b)
    push!(graph[b], a)
end

@show graph

結果

yuu@penguin:~/src/daikon/20240306$ julia graph.jl 
4 4
1 2
2 3
2 4
3 4
graph = Vector{Any}[[2], [1, 3, 4], [2, 4], [2, 3]]