Python3でグラフの実装

pythonでのグラフとその探索の実装の仕方が分からず，悲しい思いをしたのでまとめました．

グラフの入力

ノードとエッジに関する情報は，競技プログラミングでよくあるように以下の形式で与えられるとします．
ノード（頂点）数はNで，番目のノードと番目のノードをi番目のエッジが結んでいることを表しています．

N
a1 b1
・
・
・
aN bN

今回使う数値例はこちら．
ノード数７，エッジ数６のグラフを考えてみます．

7
3 6
1 2
3 1
7 4
5 7
1 4

図にするとこんな感じです．

このグラフの入力は，例えば以下のように書いて受け取ることができます．

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

さて，このようにして情報を受け取ったとすると，いま，情報を以下の形式で持っています．

n=7  #ノード数
p = [[3,6], [1,2], [3, 1], [7,4], [5,7], [1,4]] #エッジ

つぎに，このグラフをプログラミングでどう表現するのか見てみます．

グラフの表現

グラフの実装の仕方は隣接リストと隣接行列の２通りあります．
どちらも一長一短あり，隣接リストはメモリの消費量
が少ない，隣接行列は直観的に分かりやすいなどの特徴があります．

そんな隣接リストの実装は以下となります．

#隣接リスト
l = [[] for i in range(n)]
for pi in p:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
print(l)

pythonは0-originな言語なので，このような書き方をすれば当然，隣接リストの先頭要素は[]となってしまいます．
しかし，今回はそれで大丈夫です．
違和感はありますが，無理に詰めるより頂点iについての情報がそのままi番目に格納されてくれていた方が，なにかと考えやすくてコードを書く時に便利です．

重みありの場合は以下のように情報が与えられます．

n=7  #ノード数
p = [[3,6,1], [1,2,2], [3, 1,3], [7,4,4], [5,7,5], [1,4,6]]

ここで，各要素の３番目が重みを表しています．
図にするとこんな感じ．赤い数字が重みを表しています．

重みありの場合は，[繋がっている頂点, 重み]としたリストを各頂点に突っ込んで行きます．

lw = [[] for i in range(n+1)]
for path in p:
    lw[path[0]].append((path[1],path[2]))
    lw[path[1]].append((path[0],path[2]))
print(lw)

隣接行列についても重みありと重みなしでメモしておきます．
こちらは[i-1, j-1]要素をノードiとノードjの接続情報の格納場所とし，重みなしのときは「繋がっている/いない」で「0/1」の２値を，重みありのときは重みを代入するだけなので簡単です．

#重みなし
m =[ [0]*n for i in range(n)]
for path in p:
    m[path[0]-1][path[1]-1] = 1
print(m) 

#重みあり
mw =[ [0]*n for i in range(n)]
for path in p:
    mw[path[0]-1][path[1]-1] = path[2]
print(mw)