この記事は、pythonで実装しているということ、グラフがWikipediaからとってきたものであるという以外、繋がりを可視化する グラフ理論入門のほぼコピーです。
また、ほぼ同じような内容で下記もとても易しく理解できます。
グラフ
グラフとは、関係を可視化するデータ構造です。
上のグラフでいうと、1から6の数字のことを頂点(vertex)または節点(node)、頂点と頂点の結びつきを辺(edge)と呼びます。また、edgeに方向性のあるものを有向グラフ、方向性のないものを無向グラフと呼びます。
グラフを辞書で表現
グラフのデータ構造
class Graph():
def __init__(self):
""" ノードのつながりを辞書型で表現する """
self.adjacency_dict = {}
def add_vertex(self, v):
""" ノードを追加する """
self.adjacency_dict[v] = []
def add_edge(self, v1, v2):
""" ノード同士をつなぐ。"""
# 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
self.adjacency_dict[v1].append(v2)
self.adjacency_dict[v2].append(v1)
def remove_edge(self, v1, v2):
""" ノード同士のつながりを削除する。"""
self.adjacency_dict[v1].remove(v2)
self.adjacency_dict[v2].remove(v1)
def remove_vertex(self,v):
""" ノードを削除する。"""
while self.adjacency_dict[v] != []:
adjacent_vertex = self.adjacency_dict[v][-1]
self.remove_edge(v, adjacent_vertex)
del self.adjacency_dict[v]
def print_graph(self):
print(self.adjacency_dict)
グラフのノードとエッジを設定
下のグラフを設定します。
graph = Graph() graph.add_vertex(1) graph.add_vertex(2) graph.add_vertex(3) graph.add_vertex(4) graph.add_vertex(5) graph.add_vertex(6) graph.add_edge(1, 2) graph.add_edge(1, 5) graph.add_edge(2, 3) graph.add_edge(2, 5) graph.add_edge(3, 4) graph.add_edge(4, 5) graph.add_edge(4, 6) graph.print_graph()
以下のように出力されます。
{1: [2, 5], 2: [1, 3, 5], 3: [2, 4], 4: [3, 5, 6], 5: [1, 2, 4], 6: [4]}
グラフの探索
深さ優先探索
スタックを使う場合
スタックを使ってLIFOで探索を行います。
def dfs_stack(self, start, visited=None):
""" 深さ優先探索 Depth First Search スタックバージョン"""
# ノードを格納するスタック
stack = [start]
# 訪れた順番を格納
visited = []
while stack != []:
current_vertex = stack.pop()
visited.append(current_vertex)
for v in self.adjacency_dict[current_vertex]:
if v not in visited and v not in stack:
stack.append(v)
print(visited)
1から探索を行います。
graph.dfs_stack(1)
探索を行った順番です。
[1, 5, 4, 6, 3, 2]
再帰を使う場合
def dfs_rec(self, start, visited=None):
""" 深さ優先探索 Depth First Search 再帰バージョン"""
if visited is None:
visited = []
visited.append(start)
print(start)
for v in self.adjacency_dict[start]:
if v in visited:
continue
self.dfs_rec(v, visited)
１から探索を行う場合
graph.dfs_rec(1)
探索を行った順番です。
[1] [1, 2] [1, 2, 3] [1, 2, 3, 4] [1, 2, 3, 4, 5] [1, 2, 3, 4, 5, 6]
幅優先探索
キューを使ったFIFOで探索を行います。
def bfs(self, start, visited=None):
# ノードを格納するキュー
queue = collections.deque([start])
# 訪れた順番を格納
visited = []
while list(queue) != []:
current_vertex = queue.popleft()
visited.append(current_vertex)
for v in self.adjacency_dict[current_vertex]:
if v not in visited and v not in queue:
queue.append(v)
print(visited)
１から探索を行う場合
graph.bfs(1)
探索を行った順番です。
[1, 2, 5, 3, 4, 6]