クラスカル法は、素集合データ構造を使い最小全域木の問題を解くアルゴリズムです。
全域木
ある無向グラフを考えた時、このグラフの全域木とは、グラフの頂点全てを使い構成される部分グラフで、木構造になるものです。
全域木（ぜんいきぎ、英:Span...
yottagin.com
2020-02-18 12:17
Python でクラスカル法を実装します。
SciPy で最小全域木を求める時はクラスカル法を使っています。
scipy.sparse.csgraph.minimum_spanning_tree
Vertex と Edge
与えられたグラフは、頂点を Vertex クラスで、辺を Edge クラスで保持します。
また、辺の重みでソートするため、Edge には特殊メソッド__lt__を定義します。
class Vertex(object):
def __init__(self, name):
self.name = name
self.node = None
class Edge(object):
def __init__(self, from_vertex, to_vertex, weight):
self.from_vertex = from_vertex
self.to_vertex = to_vertex
self.weight = weight
def __lt__(self, other_edge):
return self.weight < other_edge.weight
素集合データ構造
素集合データ構造を定義します。
以下をのままコピーしています。
以下のスライドがダントツで分かりやすいです。
素集合データ構造
素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割し...
yottagin.com
2020-02-17 16:11
class Vertex(object):
def __init__(self, name):
self.name = name
self.node = None
class Edge(object):
def __init__(self, from_vertex, to_vertex, weight):
self.from_vertex = from_vertex
self.to_vertex = to_vertex
self.weight = weight
def __lt__(self, other_edge):
return self.weight < other_edge.weight
class Node(object):
def __init__(self, vertex, parent=None, rank=0):
self.node_name = vertex.name
self.parent = parent
self.rank = rank
class DisjointSet(object):
def __init__(self, vertex_list):
self.vertex_list = vertex_list
self.make_sets(vertex_list)
def make_sets(self, vertex_list):
for vertex in vertex_list:
self.make_set(vertex)
def make_set(self, vertex):
node = Node(vertex, parent=None, rank=0)
node.parent = node
vertex.node = node
def union(self, x_node, y_node):
x_root = self.find(x_node)
y_root = self.find(y_node)
# in the same set
if x_root == y_root:
return
if x_root.rank > y_root.rank:
y_root.parent = x_root
elif x_root.rank < y_root.rank:
x_root.parent = y_root
else:
y_root.parent = x_root
x_root.rank += 1
def find(self, node):
if node.parent != node:
node.parent = self.find(node.parent)
return node.parent
クラスカル法
疑似コードそのままです。
algorithm Kruskal(G) is
A := ∅
for each v ∈ G.V do
MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), increasing do
if FIND-SET(u) ≠ FIND-SET(v) then
A := A ∪ {(u, v)}
UNION(FIND-SET(u), FIND-SET(v))
return A
class Vertex(object):
def __init__(self, name):
self.name = name
self.node = None
class Edge(object):
def __init__(self, from_vertex, to_vertex, weight):
self.from_vertex = from_vertex
self.to_vertex = to_vertex
self.weight = weight
def __lt__(self, other_edge):
return self.weight < other_edge.weight
class Node(object):
def __init__(self, vertex, parent=None, rank=0):
self.node_name = vertex.name
self.parent = parent
self.rank = rank
class DisjointSet(object):
def __init__(self, vertex_list):
self.vertex_list = vertex_list
self.make_sets(vertex_list)
def make_sets(self, vertex_list):
for vertex in vertex_list:
self.make_set(vertex)
def make_set(self, vertex):
node = Node(vertex, parent=None, rank=0)
node.parent = node
vertex.node = node
def union(self, x_node, y_node):
x_root = self.find(x_node)
y_root = self.find(y_node)
# in the same set
if x_root == y_root:
return
if x_root.rank > y_root.rank:
y_root.parent = x_root
elif x_root.rank < y_root.rank:
x_root.parent = y_root
else:
y_root.parent = x_root
x_root.rank += 1
def find(self, node):
if node.parent != node:
node.parent = self.find(node.parent)
return node.parent
class Kruskal(object):
def __init__(self, vertex_list, edge_list):
self.vertex_list = vertex_list
self.edge_list = edge_list
self.spanning_tree = []
self.min_weight = 0
def make_min_spanning_tree(self):
disjoint_set = DisjointSet(self.vertex_list)
edge_list_sorted = sorted(self.edge_list)
for edge in edge_list_sorted:
u = edge.from_vertex
v = edge.to_vertex
if disjoint_set.find(u.node) != disjoint_set.find(v.node):
self.spanning_tree.append(edge)
disjoint_set.union(u.node, v.node)
def show_min_spanning_tree(self):
edges = []
weight = 0
for edge in self.spanning_tree:
edges.append(f'{edge.from_vertex.name}-{edge.to_vertex.name}')
weight += edge.weight
print(edges, 'weight:', weight)
テスト
以下のグラフで最小全域を求めてみます。
class Vertex(object):
def __init__(self, name):
self.name = name
self.node = None
class Edge(object):
def __init__(self, from_vertex, to_vertex, weight):
self.from_vertex = from_vertex
self.to_vertex = to_vertex
self.weight = weight
def __lt__(self, other_edge):
return self.weight < other_edge.weight
class Node(object):
def __init__(self, vertex, parent=None, rank=0):
self.node_name = vertex.name
self.parent = parent
self.rank = rank
class DisjointSet(object):
def __init__(self, vertex_list):
self.vertex_list = vertex_list
self.make_sets(vertex_list)
def make_sets(self, vertex_list):
for vertex in vertex_list:
self.make_set(vertex)
def make_set(self, vertex):
node = Node(vertex, parent=None, rank=0)
node.parent = node
vertex.node = node
def union(self, x_node, y_node):
x_root = self.find(x_node)
y_root = self.find(y_node)
# in the same set
if x_root == y_root:
return
if x_root.rank > y_root.rank:
y_root.parent = x_root
elif x_root.rank < y_root.rank:
x_root.parent = y_root
else:
y_root.parent = x_root
x_root.rank += 1
def find(self, node):
if node.parent != node:
node.parent = self.find(node.parent)
return node.parent
class Kruskal(object):
def __init__(self, vertex_list, edge_list):
self.vertex_list = vertex_list
self.edge_list = edge_list
self.spanning_tree = []
self.min_weight = 0
def make_min_spanning_tree(self):
disjoint_set = DisjointSet(self.vertex_list)
edge_list_sorted = sorted(self.edge_list)
for edge in edge_list_sorted:
u = edge.from_vertex
v = edge.to_vertex
if disjoint_set.find(u.node) != disjoint_set.find(v.node):
self.spanning_tree.append(edge)
disjoint_set.union(u.node, v.node)
def show_min_spanning_tree(self):
edges = []
weight = 0
for edge in self.spanning_tree:
edges.append(f'{edge.from_vertex.name}-{edge.to_vertex.name}')
weight += edge.weight
print(edges, 'weight:', weight)
if __name__ == '__main__':
a = Vertex('A')
b = Vertex('B')
c = Vertex('C')
d = Vertex('D')
e = Vertex('E')
f = Vertex('F')
g = Vertex('G')
edge_ab = Edge(a, b, 7)
edge_ad = Edge(a, d, 5)
edge_ba = Edge(b, a, 7)
edge_bc = Edge(b, c, 8)
edge_bd = Edge(b, d, 9)
edge_be = Edge(b, e, 7)
edge_cb = Edge(c, b, 8)
edge_ce = Edge(c, e, 5)
edge_da = Edge(d, a, 5)
edge_db = Edge(d, b, 9)
edge_de = Edge(d, e, 15)
edge_df = Edge(d, f, 6)
edge_eb = Edge(e, b, 7)
edge_ec = Edge(e, c, 5)
edge_ed = Edge(e, d, 15)
edge_ef = Edge(e, f, 8)
edge_eg = Edge(e, g, 9)
edge_fd = Edge(f, d, 6)
edge_fe = Edge(f, e, 8)
edge_fg = Edge(f, g, 11)
edge_ge = Edge(g, e, 9)
edge_gf = Edge(g, f, 11)
vertex_list = [a, b, c, d, e, f, g]
edge_list = [edge_ab, edge_ad, edge_ba, edge_bc, edge_bd, \
edge_cb, edge_ce, edge_da, edge_db, edge_de, edge_df, \
edge_eb, edge_ec, edge_ed, edge_ef, edge_eg, edge_fd, \
edge_fe, edge_fg, edge_ge, edge_gf]
kruskal = Kruskal(vertex_list, edge_list)
kruskal.make_min_spanning_tree()
# ['A-D', 'C-E', 'D-F', 'A-B', 'E-B', 'E-G'] weight: 39
kruskal.show_min_spanning_tree()
想定通りの結果になりました。
プリム法はクラスカル法と同じ最小全域木を探すアルゴリズムです。
最短経路を探すダイクストラ法にとても良く似ています。
プリム法
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象とな...
yottagin.com
2020-02-21 09:27