第Ⅲ回プロコン分科会(木、グラフについてその1)
森、木、グラフ、有向無向、頂点、辺、重み、(非)連結、(入|出)次数、隣接、パス、閉路、多重辺、自己辺、橋、関節点、根、親、子、DAG、なもり木、とか用語についての解説はその場でします。(図を書くのがめんどい)
(グラフの場合は、ある程度問題文を見ればわかるので適当にARCとかを漁ってみて)
グラフの扱い方とかアルゴリズムとかについておおざっぱに
以降、Vは頂点数、Eは辺の数を表します。
グラフの持ち方
A_iとB_iが重みC_iの辺で繋がってるとき、
A_1 B_1 C_1 A_2 B_2 C_2 ...
みたいに入ってくるとする。
隣接行列
int graph[205][205]; rep(i,E){ int a,b,c; scanf("%d%d%d",&a,&b,&c); graph[a][b] = c; graph[a][b] = c; }
楽に書ける、ワーシャルフロイド法とかはこれを使う。
Vが10^5くらいになるとメモリが死ぬので使えない。
隣接リスト
vector<pair<int,int> > graph[205]; rep(i,E){ int a,b,c; scanf("%d%d%d",&a,&b,&c); graph[a].push_back(make_pair(a,c)); graph[b].push_back(make_pair(b,c)); }
typedef long long int lli; typedef pair<lli,lli> mp; vector<mp> vs[100005]; rep(i,E){ lli a,b,c; scanf("%lld%lld%lld",&a,&b,&c); vs[a].push_back(mp(b,c)); vs[b].push_back(mp(a,c)); }
こちらの方が一般的。速い。メモリが軽い。
最短経路問題
ダイクストラ法
1つの頂点からの他の全頂点に対する最短経路が求まる。
全辺の重みが負でない時に使える。
一番早い。O(ElogV)。密なグラフ(E≈V^2)のときは、O(V^2)のアルゴリズムを使った方がよい。
priority_queue<int,vector<int>,greater<int> > que;
ベルマンフォード法
1つの頂点からの他の全頂点に対する最短経路が求まる。
負の重みの辺があっても使える。負閉路検出ができる。
O(EV)。そこそこ高速。
ワーシャルフロイド法
全ての頂点からの他の全頂点に対する最短経路が求まる。
負の重みの辺があっても使える。負閉路検出ができる。
O(V^3)で重さはそれなり。
実装がめちゃ軽いので楽に最短路を求めたいときにオススメ。
rep(k,V)
rep(i,V)
rep(j,V)
if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
その他
GDraw (グラフの可視化ができる)
