Pythonで学ぶアルゴリズム（10/18）

　アルゴリズムを学ぶのにPythonの学習も兼ねて

Ｐｙｔｈｏｎで学ぶアルゴリズムとデータ構造 (データサイエンス入門シリーズ)

を参照していく。

前回

power-of-awareness.com

6.　グラフ構造

　ヒトのつながりを表現する手段であるグラフ理論に基づくグラフ構造が利用し得る。

6.1　グラフの基礎

　グラフは頂点(vertex)/節点(nodel)と辺(edge)/枝(branch)など呼ばれる構造から成り立つ。

　ある2つの頂点が1つの辺でつながっているとき、これらの頂点は隣接している(adjacent)という。2つの辺が1つの頂点を共有しているときにも隣接しているという。ある辺の両端の頂点を端点という。ある頂点から出ている辺の数を次数(degree)という。
　グラフにおけるある2つの頂点を結ぶ辺の集合を道(path)という。すべての頂点の間に道があるグラフを連結グラフという。以下のような場合は連結グラフでない。連結グラフが複数存在するグラフでは、連結成分がつ存在するという*1。

　木構造はグラフの1つで、任意の頂点ペアの道が1つしかないようなグラフである。いくつかの頂点を経て出発した頂点に戻る道が存在するとき、その道を閉路という。定義から明らかに木は閉路をもたない。複数の木からなるグラフを森という。
　辺に向きがあるグラフを有向グラフといい、向きが無い場合を無向グラフという。

6.2　グラフを表現するデータ構造

　グラフ構造を表現するための代表的なデータ構造には、隣接行列と隣接リストがある。隣接行列は行および列が辺に相当し、各成分には対応する頂点同士に辺が存在すれば、存在しなければを格納している。無向グラフの場合、隣接行列は対称行列になる。
　それぞれの頂点から見て隣接する頂点を連結リストなどで保持するデータ構造を隣接リストと言う。

##################
### グラフ構造 ###
##################

# NetworkXを使ってみる
import random
import networkx as nx
%matplotlib inline

graph = nx.Graph()
graph.add_edge(5,6)
graph.add_edge(6,7)

nx.draw_networkx(graph)

# グラフの生成
def generate_graph(n, m):
    """ n個の頂点とm個の辺の持つグラフを作成する """
    graph_data = [[0] * n for i in range(n)]
    edge_set = set()
    
    while len(edge_set) < m:
        i, j = random.sample(range(n), 2)
        if i > j:i, j = j, i
        edge_set.add((i,j))
        graph_data[i][j] = graph_data[j][i] = 1
    return graph_data, edge_set

# テストデータを生成
random.seed(6)
node_num = 16
edge_num = 20
my_graph, edge_set = generate_graph(node_num, edge_num)

# NetworkXを使ってグラフを描画する
graph = nx.Graph()
for u,v in edge_set:
    graph.add_edge(u, v)
nx.draw_networkx(graph) 

6.3　連結グラフにおける探索

　連結グラフから連結成分を探索することを考える。探索の方向性は2つ存在する：

• 幅優先探索：近い頂点から順に到達可能な頂点を網羅的に探索していく
• 深さ優先探索：可能な限り進むことのできる道をしらみつぶしに探していく

6.4　幅優先探索

6.4.1　キュー

　幅優先探索を扱う際に有用な概念がキュー(queue)である。玉突き的にデータを蓄積していき、先頭のデータから処理を行っていくものである。

##############################
### dequeを用いたqueue構造 ###
##############################

from collections import deque

queue = deque([])
queue.append(1)
queue.append(2)
queue.append(3)

print(queue)

deque([1,2,3])

print(queue.popleft())
print(queue)

6.4.2　キューを用いた幅優先探索

・入力：スタートの頂点、グラフを表現する隣接行列
・出力：頂点から到達できるすべての頂点

手続き：

1. 作業用のキューおよび到達した頂点を保存するための集合それぞれにを追加する。
2. キューから頂点を取り出す。
3. 取り出した頂点の隣にあるすべての頂点に対して、もしに入っていなければの双方にその頂点を追加する。
4. ならばを出力して終了する。そうでなければ.に戻る。

##################
### グラフ構造 ###
##################

# NetworkXを使ってみる
import random
import networkx as nx
%matplotlib inline

graph = nx.Graph()
graph.add_edge(5,6)
graph.add_edge(6,7)

nx.draw_networkx(graph)

# グラフの生成
def generate_graph(n, m):
    """ n個の頂点とm個の辺の持つグラフを作成する """
    graph_data = [[0] * n for i in range(n)]
    edge_set = set()
    
    while len(edge_set) < m:
        i, j = random.sample(range(n), 2)
        if i > j:i, j = j, i
        edge_set.add((i,j))
        graph_data[i][j] = graph_data[j][i] = 1
    return graph_data, edge_set

# テストデータを生成
random.seed(6)
node_num = 16
edge_num = 20
my_graph, edge_set = generate_graph(node_num, edge_num)

# NetworkXを使ってグラフを描画する
graph = nx.Graph()
for u,v in edge_set:
    graph.add_edge(u, v)
nx.draw_networkx(graph) 

from collections import deque

def breadth_first_search(start, W):
    """ 隣接行列Wで表現されるグラフについて
    startから到達可能なnodeの一覧を返す
    """
    # リストをキューにする
    work_queue = deque([])
    visited = set()
    # 初期化
    work_queue.append(start)
    visited.add(start)
    while work_queue:
        print(work_queue)  # work_queueの中身を表示する
        # 今いる頂点
        here = work_queue.popleft()
        # 今いる頂点に隣接する頂点すべてを処理する
        for i, node in enumerate(W[here]):
            # 隣接しなければ何もしない
            if node == 0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)
    return visited

breadth_first_search(1, my_graph)
breadth_first_search(10, my_graph)

次回

power-of-awareness.com

*1:以下では2つ存在する。