PSM

Pプログラミング S初心者の Mメモ書き

Python3でグラフの実装&深さ優先探索・幅優先探索の実装

競技プログラミングのある問題に取り組んでいるとき,解き方はわかったのに,pythonでのグラフとその探索の実装の仕方が分からず,悲しい思いをしたのでまとめました.

ちょくちょく更新していきます.

グラフの入力

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

N
a1 b1
・
・
・
aN bN

今回使う数値例はこちら.
ノード数7,エッジ数6のグラフを考えてみます.

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

図にするとこんな感じです.
f:id:muromura:20170716021330p:plain


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

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]] #エッジ

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

グラフの表現

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

競技プログラミングにおいてはメモリ消費量の制限があるため,隣接リストを使うことが多いようです.
そんな隣接リストの実装は以下となります.

#隣接リスト
l = [[] for i in range(n)]
for pi in p:  #0-originedに注意
    l[pi[0]-1].append(pi[1]-1)
    l[pi[1]-1].append(pi[0]-1)
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]]

ここで,各要素の3番目が重みを表しています.
図にするとこんな感じ.赤い数字が重みを表しています.
f:id:muromura:20170817181213p:plain


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

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」の2値を,重みありのときは重みを代入するだけなので簡単です.

#重みなし
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) 

グラフの探索

グラフの探索にはいくつかの方法がありますが,そのうち深さ優先探索幅優先探索を実装したものが以下となります.
ここでは頂点ナンバーを訪れた順に出力する関数を定義しています.

深さ優先探索

#深さ優先探索
def dfs(Graph, Start, Visited=None):
    if (Visited==None):  Visited = [] #開始点のときに探索済みリストをつくる
    Visited.append(Start)  #現在の頂点を探索済みリストに加える    
    print(Start, "\n", Visited)  #現在の頂点と探索済みリストを表示
    for Next in Graph[Start]:  #次に探索する頂点の候補
        if ( Next in Visited ):  continue  #訪問済みリストにある頂点は飛ばす
        dfs(Graph, Next, Visited)  #再帰

#頂点0(1)から探索
dfs(l, 0)

実行結果

0 
 [0]
1 
 [0, 1]
2 
 [0, 1, 2]
5 
 [0, 1, 2, 5]
3 
 [0, 1, 2, 5, 3]
6 
 [0, 1, 2, 5, 3, 6]
4 
 [0, 1, 2, 5, 3, 6, 4]

幅優先探索

#幅優先探索     
def bfs(Graph, Start):
    visited= {Start: None} #親子ノードを対にした訪問済みリスト
    unvisited = [Start]  #現在の頂点から見た未訪問リスト
    while unvisited: #未訪問リストにある点それぞれについて考える
        Now = unvisited[0]
        unvisited = unvisited[1:]
        print(Now, "\n", visited,"\n", unvisited)  #現在のノードと訪問済みリスト
        for Next in Graph[Now]:  #次に探索する頂点の候補
            if not(Next in visited):  
                unvisited.append(Next)  #新しい候補点をリストに追加
                visited[Next] = Now  #親子ノードを記入
    return visited

bfs(l,0)

出力結果

0 
 {0: None} 
 []
1 
 {0: None, 1: 0, 2: 0, 3: 0} 
 [2, 3]
2 
 {0: None, 1: 0, 2: 0, 3: 0} 
 [3]
3 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2} 
 [5]
5 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3} 
 [6]
6 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3} 
 []
4 
 {0: None, 1: 0, 2: 0, 3: 0, 5: 2, 6: 3, 4: 6} 
 []
Out[16]:
{0: None, 1: 0, 2: 0, 3: 0, 4: 6, 5: 2, 6: 3}

Pythonはzero based indexingなので,i番目の頂点がi-1として表されることに注意が必要です.

まとめ

とりあえず今は訪問順にそのまま出力しているだけで,ほとんど何もしていません.
自由に探索をができるようになるまでは,もう少し習熟が必要なようです.