グラフグラフ, 有向グラフ, 閉路, 最小値, BFS, ベルマンフォード法, ダイクストラ法

アルゴリズム

最小コストの閉路:

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

2020年3月30日グラフグラフ, 重み付きグラフ

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。

ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。

負の辺が含まれていても動作する
負の閉路がある場 ...

グラフグラフ, 貪欲法, 最小全域木, プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月23日グラフグラフ, 貪欲法, クラスカル法, 最小全域木

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月20日グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, Union-Find, 連結成分のサイズ, 同じ連結成分か判定

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, 連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

2020年3月13日グラフグラフ, , 競プロ, 無向グラフ, 重み付きグラフ, 木の直径

木に存在する2つノード間の最大距離を木の直径と言います。

重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。

重み無しの木の例:

以下は直径が5となる木の例で ...

2020年3月7日グラフグラフ, 競プロ, 重み付きグラフ, 単一始点最短経路, 最短経路, ダイクストラ法, ヒープ, 優先度付きキュー, 貪欲法

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては

計算量が \(O(|E| \l ...

2020年3月7日グラフグラフ, 競プロ, 重み付きグラフ, ベルマンフォード法, 単一始点最短経路, 最短経路, 負の閉路, 負の辺

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、

負の辺が含まれているような場合でも適用 ...

2020年3月3日AtCoderグラフ, 競プロ, 連結成分, Union-Find

問題概要

N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。

まだ友達関係ではない
ブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...