ここではグラフ理論とグラフ探索を学ぶ.
下図のように,丸が線で結ばれている図をグラフ理論的グラフという.
# これは描画のためのコードなので,気にしなくて良い.
import networkx as nx
import matplotlib.pyplot as plt
% matplotlib inline
ptersen = nx.petersen_graph()
nx.draw(ptersen)
丸を「頂点」,線を「枝」とよぶ. グラフ理論的グラフにおいては,頂点が枝でどのように結ばれているかという「構造」が大事であり,描画における頂点の座標などは大事でない.
例として,以下のようなグラフを考える.
# これは描画のためのコードなので,気にしなくて良い.
G = nx.Graph()
for i in range(1, 10):
G.add_node(i, position=((i - 1) % 3, 2 - (i - 1) // 3))
G.add_edge(1, 2)
G.add_edge(1, 4)
G.add_edge(2, 3)
G.add_edge(2, 5)
G.add_edge(3, 6)
G.add_edge(4, 5)
G.add_edge(4, 7)
G.add_edge(5, 6)
G.add_edge(5, 8)
G.add_edge(7, 8)
%matplotlib inline
fig, ax = plt.subplots()
ax.set_axis_off()
nx.draw_networkx(G, pos=nx.get_node_attributes(G, 'position'), with_labels=True, node_color='w')
このグラフは,①から⑨の頂点からなるグラフである. ⑨は他のどの頂点とも結ばれていない.
このグラフの例からわかる通り,グラフのすべての頂点が枝を介してつながっているとは限らない.
枝を介して行き来できる頂点のグループ分けを考える.
グラフ探索問題は以下のような問題である.
例えば,入力として上記のグラフと始点①が与えられたら,出力は{①,②,③,④,⑤,⑥,⑦,⑧}である. 例えば,入力として上記のグラフと始点⑨が与えられたら,出力は{⑨}である.
グラフ探索問題は,以下の手続き(アルゴリズム)で解ける.
このグラフ探索アルゴリズムをPythonで実装する.
Python上でグラフ探索するためには,まず,グラフを何らかの形で覚えなければいけない. 上記のグラフ探索アルゴリズムでは,グラフの構造のうち
がわかるようになっていればよい.(他の情報は特に使わない.)
よって,それぞれの頂点の隣接頂点を辞書で覚えることにする. 例えば,前出の9つの頂点からなるグラフならば以下の辞書adjでよい.
adj = { # ここでは頂点の名前を数字で表すことにする.別に文字列でも良い.
1: [2, 4], # 頂点①の隣接頂点は②と④という意味である.
2: [1, 3, 5],
3: [2, 6],
4: [1, 5, 7],
5: [2, 4, 6, 8],
6: [3, 5],
7: [4, 8],
8: [5, 7],
9: [],
}
このように覚えれば,例えば頂点⑤の隣接頂点を知りたければ
adj[5]
[2, 4, 6, 8]
とすればよい.
これでグラフを覚えられたので,早速グラフ探索アルゴリズムをPythonで実装する.
「これから訪れたい頂点」はPythonのsetを用いて覚えることにする.
def graph_scanning(G, s):
C = set([s]) # Cはこれまでに訪れた頂点+その隣接頂点
S = set([s]) # Sはこれから訪れたい頂点
while len(S) > 0: # Sが空集合でないならば
v = S.pop() # Sから1つ取り出してvとする.
for w in G[v]: # vの隣接頂点wに関して,
if w not in C: # もし,WがCに含まれないならば,
C = C | set([w]) # C |= set([w]])でも良い.
S = S | set([w]) # S |= set([w])でも良い.
return C # 最後にCを出力して終了する.
実際に試してみる.
graph_scanning(adj, 1)
{1, 2, 3, 4, 5, 6, 7, 8}
graph_scanning(adj, 9)
{9}
良さそうである.
グラフ探索アルゴリズムのうち,これから訪れたい頂点をスタックで覚えたものを深さ優先探索(Depth First Search略してDFS)という
以下に深さ優先探索をstack_DFSとして定義する.
def stack_DFS(G, s):
C = [s] # 別に集合じゃなくてリストでも良い.
S = [s] # このSはスタックのつもりである.スタックをリストで表現する.
while len(S) > 0:
v = S.pop() # スタックなので,最後に加えたもの(すなわちリストの最後)を1つ取り出す.
for w in G[v]:
if w not in C:
C += [w]
S += [w]
return C
実際に試してみる.
stack_DFS(adj, 1)
[1, 2, 4, 3, 5, 7, 6, 8]
stack_DFS(adj, 9)
[9]
結果は,集合とリストの違いはあるが,同じになる.
ただし,スタックを用いると,計算の途中で覚える「これから訪れたい頂点」の集合があまり大きくならないことが経験的に知られている.