読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

c++11でグラフ理論

競プロで頻繁にグラフが絡む問題が出題されます.
隣接リストvector<vector<Edge>>を継承してグラフの様々な値を求めることができるクラスを作ってみました.

使い方

・宣言

graph<T> g((int)n):

重みの型がTの,頂点の数がn個の隣接グラフの宣言.

・辺の挿入

g.direct(src,dst,w) | g.direct(src,dst)

起点src, 終点dst, 重さwの有向辺の挿入.

g.undirect(src,dst,w) | g.undirect(src,dst)

起点src, 終点dst, 重さwの無向辺の挿入.

・直径

g.diamater()

グラフの直径を求める.

・距離

g.dijkstra(src)

srcから全頂点の距離をダイクストラ法で求める.

g.bellmanFord(src)

srcから全頂点の距離をベルマンフォード法で求め負閉路の有無の判定と共に返す.

・全域木

g.MST(root)

rootを根とする最小全域(無向)木をPrimのアルゴリズムで求める.

g.MSA(root)

rootを根とする最小全域有向木をChu-Liu/Edmondのアルゴリズムで求める.

・関節点/橋

g.APs()

関節点を求める.

g.bridges()

橋を求める.


graph class