Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@HMMNRST

2部グラフの判定の練習：BFS・DFS・Union-Find

Posted at

2部グラフの判定をきちんとやったことが無かったので練習することにした。

また、通常のグラフ探索の方法で気になる点があり、Union-Findの要領で解決できそうだったので、これも試してみた。

グラフ探索

2部グラフの判定をするには、グラフの頂点に2値（例えば 0 と 1 ）を振ってみて、矛盾が生じるか調査する。「辺で繋がった2頂点は逆の値」という規則があるため、適当な頂点に値を決め打ちしたら隣接する頂点を貪欲に埋めていけばいい（探索順序は問わない）。隣接する頂点に既に値が振ってあれば、それが期待通りかどうか検査する。

1セットの探索（例えば下記コードの bfs() 1回の呼び出し）では開始地点と連結な頂点しか調べられないので、未調査の頂点を探して何セットか探索する。

幅優先探索（BFS）

開始地点から近い順に頂点を埋めていくパターン。

bipartite_bfs.rb
n, m = gets.split.map!(&:to_i)
edges = Array.new(m) { gets.split.map!(&:to_i).map!(&:pred) }

@nbrs = Array.new(n) { [] }
edges.each do |i, j|
	@nbrs[i] << j
	@nbrs[j] << i
end

##########

@parity = Array.new(n)

def bfs(k)
	@parity[k] = 0
	queue = [k]

	while (i = queue.shift)
		expected = @parity[i] ^ 1

		@nbrs[i].each do |j|
			if @parity[j]
				raise "Not bipartite" if @parity[j] != expected
				next
			end

			@parity[j] = expected
			queue << j
		end
	end
end

begin
	n.times { |k| @parity[k] || bfs(k) }
	puts :Yes
rescue RuntimeError
	puts :No
end

深さ優先探索（DFS）

再帰で書けば短く済むものの、スタックオーバーフローの危険がある。

bipartite_dfs.rb
n, m = gets.split.map!(&:to_i)
edges = Array.new(m) { gets.split.map!(&:to_i).map!(&:pred) }

@nbrs = Array.new(n) { [] }
edges.each do |i, j|
	@nbrs[i] << j
	@nbrs[j] << i
end

##########

@parity = Array.new(n)

def dfs(i, expected = 0)
	if @parity[i]
		raise "Not bipartite" if @parity[i] != expected
		return
	end

	@parity[i] = expected
	@nbrs[i].each { |j| dfs(j, expected ^ 1) }
end

begin
	n.times { |k| @parity[k] || dfs(k) }
	puts :Yes
rescue RuntimeError
	puts :No
end

素集合データ構造（Union-Find）

グラフ探索の方法で、連結でない頂点には適当な値を仮決めしているのが気になった。もし後から辺が追加されて連結になったら、1/2の確率で破綻してしまい、もう一度値を振り直す必要がある。仮決めではなく上手いこと相対的な偶奇性（同じ値なのか逆の値なのか）だけ記憶しておけば、辺が追加される状況にも対処できるのではないかと思った。

連結を扱える高速なアルゴリズムを考えたら、Union-Findが思い浮かんだ。この処理の中に2部グラフが成立していることの確認を追加してみた（Union-Find自体はAtCoder Libraryを参考にした）。

  • 親ノードに対する偶奇性を記憶しておく
    • 代表元は便宜上、自分自身に対する偶奇（なので必ず偶）とする
  • 代表元の取得 find() では親ノードを変えるので、記憶している偶奇性も更新する
    • 具体的には「 k ← j ← i 」という連鎖から「 k ← i 」の関係を求める
  • グループの併合 union() では、代表元同士の偶奇を考えるよう変換する
    • i と j を連結する（2部グラフなので関係が奇であることを要請する）際は、それらの代表元 ii と jj の間にリンクを張るが、この関係の偶奇を求める必要がある
    • i と j が既に連結なら ii == jj であり、自分自身との関係は偶でなければ矛盾になる

辺が追加される状況に対応できるということで、事前に隣接する頂点のリスト（前節の @nbrs ）を作る必要は無く、片っ端から辺の情報を与えていけばいい。

bipartite_dsu.rb
n, m = gets.split.map!(&:to_i)
edges = Array.new(m) { gets.split.map!(&:to_i).map!(&:pred) }

##########

@parent = Array.new(n, -1)
@parity = Array.new(n, 0)  # relative to @parent[i]

def find(i)
	return i if @parent[i] < 0

	j = @parent[i]
	k = find(j)
	@parity[i] ^= @parity[j]
	@parent[i] = k
end

def union(i, j)
	ii = find(i)
	jj = find(j)
	expected = 1 ^ @parity[i] ^ @parity[j]

	if ii == jj
		raise "Not bipartite" if expected != 0
		return
	end

	ii, jj = jj, ii if -@parent[ii] < -@parent[jj]
	@parent[ii] += @parent[jj]
	@parent[jj] = ii
	@parity[jj] = expected
	nil
end

begin
	edges.each { |i, j| union(i, j) }
	# n.times { |k| find(k) }  # fix @parity: relative to find(i)
	puts :Yes
rescue RuntimeError
	puts :No
end

テスト用の入力

正しく動作するか、高速に（ O(n) 程度で）求まるか、などを確かめるためにテストデータを生成したい。頂点や辺の数は自由に指定できるようにする。

入力の作成とテスト実行
ruby bipartite_test_random.rb 100_000 100_000 > input.txt
time ruby bipartite_bfs.rb < input.txt
time ruby bipartite_dfs.rb < input.txt
time ruby bipartite_dsu.rb < input.txt

※これはプログラムの実行時間全体を計っているので、判定アルゴリズムのみにかかった時間は見れない。

ランダムな辺

適当に選んだ2頂点に辺をひく（自己ループは除く）。辺の数 m を大きくすれば高確率で2部グラフではなくなる。

bipartite_test_random.rb
n, m = ARGV.map(&method(:Integer))
raise "n must be positive" if n <= 0
raise "m must be non-negative" if m < 0

puts "#{n} #{m}"
m.times do
	i = rand(n)
	j = i + 1 + rand(n - 1)
	puts "#{i + 1} #{j % n + 1}"
end

2部グラフ

事前に頂点を2グループに分けておいて、必ずグループをまたぐよう辺をひく。

bipartite_test_true.rb
n1, n2, m = ARGV.map(&method(:Integer))
raise "both n1 and n2 must be positive" if n1 <= 0 || n2 <= 0
raise "m must be non-negative" if m < 0

n = n1 + n2
grp1 = [*1..n].shuffle!
grp2 = grp1.pop(n2)

puts "#{n} #{m}"
m.times do
	i, j = grp1.sample, grp2.sample
	i, j = j, i if rand < 0.5
	puts "#{i} #{j}"
end

閉路グラフ

n が偶数のとき2部グラフ。深さ優先探索の再帰を効率よく殺すためのパターンで、どこから開始しても深さが n に達する。手元の環境（ RUBY_THREAD_VM_STACK_SIZE=1048576 ）では n = 3743 で死んだ。

bipartite_test_cycle.rb
n, * = ARGV.map(&method(:Integer))
raise "n must be positive" if n <= 0

order = [*1..n].shuffle!
order << order[0]
pairs = order.each_cons(2).to_a.shuffle!

puts "#{n} #{n}"
pairs.each do |i, j|
	i, j = j, i if rand < 0.5
	puts "#{i} #{j}"
end

木・森

必ず2部グラフ。

bipartite_test_forest.rb
n, m = ARGV.map(&method(:Integer))
raise "n must be positive" if n <= 0
raise "m must be non-negative" if m < 0
raise "m must be less than n" if m >= n

order = [*1..n].shuffle!
pairs = Array.new(m) do |i|
	j = rand(n - i - 1) + i + 1
	[order[i], order[j]]
end
pairs.shuffle!

puts "#{n} #{m}"
pairs.each do |i, j|
	i, j = j, i if rand < 0.5
	puts "#{i} #{j}"
end
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?