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

第Ⅲ回プロコン分科会(木、グラフについてその1)

森、木、グラフ、有向無向、頂点、辺、重み、(非)連結、(入|出)次数、隣接、パス、閉路、多重辺、自己辺、橋、関節点、根、親、子、DAG、なもり木、とか用語についての解説はその場でします。(図を書くのがめんどい)

Online Programming Lesson

(グラフの場合は、ある程度問題文を見ればわかるので適当に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];

最小全域木問題

クラスカル

Union Find木を使えば実装がめちゃ楽。

プリム法

使ったためしがない...

その他

GDraw (グラフの可視化ができる)