これを、例にしよう。
教科書にはだいたい最初に隣接行列が書いてある。2点をそれぞれ行と列と考えて、その点同士が辺でつながっていれば要素を1、つながっていなければ0とする。これを隣接行列という。Pythonで書くと、
g = [
[ 0, 0, 1, 1 ],
[ 0, 0, 0, 0 ],
[ 1, 0, 0, 1 ],
[ 1, 0, 1, 0 ]
];
しかし、これはあまりに効率が悪い。
代わりに、点に対しどの点が直接辺で繋がっているかを表す。
g = [
[ 2, 3 ],
[ ],
[ 0, 3 ],
[ 0, 2 ]
];
辺1つにつき2つデータがあるが、しょうがない。
これを元にクラスを作った。
class cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
def add_edge(self, vs, ve):
if self.exists_edge(vs, ve):
return False
else:
self.g[vs].append(ve)
self.g[ve].append(vs)
return True
def exists_edge(self, vs, ve):
for k in self.g[vs]:
if k == ve:
return True
return False
def disp(self):
for e in self.g:
print e
連結の判定
点の数だけの要素数の配列を作っておき0を入れておく。まず点0から始めて、辿った点に1を入れる。点0に隣接する点でまだ辿っていない点は1にしてスタックに入れる。点0が終わったらスタックから点を取り出して、スタックが空になるまで同じことを繰り返す。最後にすべての点が1になっていたら連結。
5点で4辺は25/42の確率で連結だったが、4200回ランダムにグラフを作って連結判定したら、2510回が連結だった。
from random import *class cGraph:
def __init__(self, n):
self.n = n
self.g = [ ];
for i in range(n):
self.g.append([ ])
def add_edge_at_random(self):
while True:
vs = randint(0, self.n - 1)
while True:
ve = randint(0, self.n - 1)
if vs != ve:
break
if self.add_edge(vs, ve):
return
def add_edge(self, vs, ve):
if self.exists_edge(vs, ve):
return False
else:
self.g[vs].append(ve)
self.g[ve].append(vs)
return True
def exists_edge(self, vs, ve):
for k in self.g[vs]:
if k == ve:
return True
return False
def is_connective(self):
a = [ 0 ] * self.n
a[0] = 1
stk = [ 0 ]
while stk:
vs = stk.pop()
for ve in self.g[vs]:
if a[ve] == 0:
a[ve] = 1
stk.append(ve)
for b in a:
if b == 0:
return False
return True
def disp(self):
for e in self.g:
print e
m = 5
n = 4
seed(m)counter = 0
for k in range(4200):
g = cGraph(m)
for i in range(n):
g.add_edge_at_random()
if g.is_connective():
counter += 1
print counter
