ホームに戻る
TopCoder の傾向と対策7(C++編:グラフ)
0、はじめに
グラフはある状態からある状態に移動できるか?の構造を持っている。
例えば、状態0から状態1へ移動できる、などである。
グラフを用いた問題は TopCoder ではよく出題される。
ダイクストラ法などグラフを用いたアルゴリズムもいくつかある。
グラフと動的計画法を同時に使用する問題などもある。
傾向としてグラフは単なる動的計画法の問題よりも難易度が高い。
1、グラフ
グラフはある状態からある状態へ移動する図が書ける。
図:
0 - 1 - 2 - 4
|
3
例えば、上図は 0 から 1 、1 から 2 への移動が可能。
また、2 から 3 、2 から 4 への移動が可能である。
このとき地点を「頂点」、線を「辺」と呼ぶ。
グラフの問題はまずグラフの条件が重要になる。
すべての頂点が辺で繋がっているかどうか?
辺の進行方向が決まっているかどうか?
辺をたどるとまた同じ頂点にもどる閉路が含まれるか?
これらの条件によって解法が異なるので注意する。
問題としてはまずグラフを作成し、
全探索、メモ化再帰、DP、数え上げ
などが考えられる。
グラフは問題によっては既に作成されているものもあるが、
作成する場合は配列とリストを使う2通りがある。
それぞれ特徴が違うので使い分ける必要がある。
2、木の直径
閉路を含まないグラフをDAGと呼ぶ。
頂点がN個であれば辺は必ずN-1個である。
DAGのある2点を選びその距離がいちばん長いとき、
その長さを木の直径と呼ぶ。
求め方は2回の深さ優先探索で求まる。
まず任意の頂点から最も遠い頂点を探す、
次にその頂点から最も遠い頂点を探す。
2回目の深さ優先探索の距離が木の直径である。
3、最短経路問題
6つの頂点と9つの辺があるグラフがある。
各辺には進行方向は定められておらず、
各辺を通る際には必要なコストが与えられている。
頂点0から頂点5までたどり着くための最小コストを求めよ?
#define V 6
#define E 9
int e[3][E] = {
{0, 0, 1, 1, 2, 2, 3, 3, 4}, // 頂点元
{1, 2, 2, 3, 3, 4, 4, 5, 5}, // 頂点先
{2, 7, 5, 3, 1, 3, 6, 5, 1} // コスト
};
int mn[V];
int flag[V];
// ここからグラフを配列に作成
int m[V][V];
for(int i = 0; i < V; i++){
for(int r = 0; r < V; r++){
m[i][r] = 9999;
}
}
for(int i = 0; i < E; i++){
m[e[0][i]][e[1][i]] = e[2][i];
m[e[1][i]][e[0][i]] = e[2][i];
}
// 最短距離と頂点のフラグを初期化
for(int i = 0; i < V; i++)mn[i] = 9999;
for(int i = 0; i < V; i++)flag[i] = 0;
// 頂点0から頂点0への最小コストは0
mn[0] = 0;
for(;;){
int v = -1;
// フラグが0でコストが最小の頂点を探す
for(int i = 0; i < V; i++){
if(flag[i] == 0){
if(v == -1){
v = i;
}
else{
if(mn[i] < mn[v]){
v = i;
}
}
}
}
// すべての頂点を使った場合は終了
if(v == -1)break;
// 使った頂点のフラグを 1 に
flag[v] = 1;
// コストを使っても結果が小さくなれば更新
for(int i = 0; i < V; i++){
if(mn[i] > mn[v] + m[v][i]){
mn[i] = mn[v] + m[v][i];
}
}
}
解は mn[5] に入っている。
以上のアルゴリズムを「ダイクストラ法」と呼ぶ。
開始頂点を定めるとそれ以外のすべての頂点への最小コストを求める。
単に最短移動回数を求めるならコストをすべて 1 にすれば良い。
計算量は V * V である。
次のように変更すると E * log(V) まで計算量を減らせる。
最小値から取り出す priority_queue を用いている。
#define V 6
#define E 9
typedef struct{
int to;
int cost;
}edge;
typedef pair<int, int> P;
int e[3][E] = {
{0, 0, 1, 1, 2, 2, 3, 3, 4},
{1, 2, 2, 3, 3, 4, 4, 5, 5},
{2, 7, 5, 3, 1, 3, 6, 5, 1}
};
int mn[V];
// ここからグラフをリストに作成
vector<edge> m[V];
for(int i = 0; i < E; i++){
edge ed;
ed.to = e[1][i];
ed.cost = e[2][i];
m[e[0][i]].push_back(ed);
ed.to = e[0][i];
ed.cost = e[2][i];
m[e[1][i]].push_back(ed);
}
for(int i = 0; i < V; i++){
for(int r = 0; r < m[i].size(); r++){
edge ed = m[i][r];
cout << i << ":" << ed.to << endl;
}
}
for(int i = 0; i < V; i++)mn[i] = 9999;
int start = 0;
mn[start] = 0;
priority_queue<P, vector<P>, greater<P> >que;
que.push(P(0, start)); // 最短距離 0 と開始頂点 0
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(mn[v] < p.first)continue;
for(int i = 0; i < m[v].size(); i++){
edge ed = m[v][i];
if(mn[ed.to] > mn[v] + ed.cost){
mn[ed.to] = mn[v] + ed.cost;
que.push(P(mn[ed.to], ed.to));
}
}
負のコストがあるとき「ダイクストラ法」は使えません。
負の値があるとある地点でコストの大きい方向にさかのぼっても、
負のコストを経過することで結果的に最小になる場合があるからです。
このときは「ベルマンフォード法」を使います。
「ベルマンフォード法」では
閉路を回転することで無限にコストが下がる負の閉路の検出もできます。
計算量は V * E になる。
「ベルマンフォード法」のコードは省略します。
「ワーシャルフロイド法」はすべての地点での最小コストを求める。
負のコストがあっても可能である。
負の閉路は結果に負の値があれば負の閉路があるといえる。
ただし、計算量は V * V * V になる。
#define V 6
#define E 9
int e[3][E] = {
{0, 0, 1, 1, 2, 2, 3, 3, 4}, // 頂点元
{1, 2, 2, 3, 3, 4, 4, 5, 5}, // 頂点先
{2, 7, 5, 3, 1, 3, 6, 5, 1} // コスト
};
// ここからグラフを配列に作成
int m[V][V];
for(int i = 0; i < V; i++){
for(int r = 0; r < V; r++){
if(i == r){
m[i][i] = 0; // m[i][i] = 0 であること
}
else{
m[i][r] = 9999; // 十分に大きな数値
}
}
}
for(int i = 0; i < E; i++){
m[e[0][i]][e[1][i]] = e[2][i];
m[e[1][i]][e[0][i]] = e[2][i];
}
for(int k = 0; k < V; k++){
for(int i = 0; i < V; i++){
for(int j = 0; j < V; j++){
if(m[i][j] > m[i][k] + m[k][j]){
m[i][j] = m[i][k] + m[k][j];
}
}
}
}
解は m の配列内にある。
4、最小全域木問題
すべての村を行き来する道を作る計画がある。
いくつかの村をつなぐにはそれぞれ異なるコストがかかる。
それぞれの村は必ずひとつの経路で行き来できるが、
複数の経路で繋がっている必要は無い。
このとき必要な最小のコストは?
例えば、下図のような6つの村とコスト()内が存在するとき、
村 2 と 村 3 をつなぐ道を作らなければ最小コストは 13 である。
(4) (3) (4)
0 - 1 - 2 - 3
(2)| |(3)
4 - 5
(1)
考え方はダイクストラ法に似ている。
プリム法と呼ぶ。
計算量は V * V である。
priority_queue を使えば E * log(V) まで計算量を減らせる。
#define V 6
#define E 6
int e[3][E] = {
{0, 1, 2, 2, 3, 4}, // 頂点元
{1, 2, 3, 4, 5, 5}, // 頂点先
{4, 3, 2, 4, 1, 3} // コスト
};
// ここからグラフを配列に作成
int m[V][V];
for(int i = 0; i < V; i++){
for(int r = 0; r < V; r++){
if(i == r){
m[i][i] = 0; // m[i][i] = 0 であること
}
else{
m[i][r] = 9999; // 十分に大きな数値
}
}
}
for(int i = 0; i < E; i++){
m[e[0][i]][e[1][i]] = e[2][i];
m[e[1][i]][e[0][i]] = e[2][i];
}
int mncost[V];
int flag[V];
for(int i = 0; i < V; i++){
mncost[i] = 9999;
flag[i] = 0;
}
mncost[0] = 0;
int res = 0;
for(;;){
int v = -1;
for(int i = 0; i < V; i++){
if(flag[i] == 0){
if(v == -1){
v = i;
}
else{
if(mncost[i] < mncost[v]){
v = i;
}
}
}
}
if(v == -1){
break;
}
flag[v] = 1;
res += mncost[v];
for(int i = 0; i < V; i++){
mncost[i] = min(mncost[i], m[v][i]);
}
}
解は res になる。
5、トポロジカルソート
例えば次のようなグラフがあるとする。
0→1→2→3
↓ ↑ ↓
4→5→6
このグラフを必ず左から右に移動する一直線のグラフに並べ替える。
この方法をトポロジカルソートと呼ぶ。
トポロジカルソートを行うとDPに利用できる。
トポロジカルソートを行うにはいろいろな条件がある。
有向グラフであること。
先頭は出発しかしない点であること。
循環しないこと。
また、ソートの結果は一通りとは限らない。
次の例では再帰を使って終点から頂点を確定している。
循環を検出しないので注意。
#define V 7
int m[V][V];
int flag[V];
vector<int> v;
void f(int n){
if(flag[n] == 0){
flag[n] = 1;
for(int i = 0; i < V; i++){
if(m[n][i] == 1){
f(i);
}
}
v.push_back(n);
}
}
memset(m, 0, sizeof(m));
memset(flag, 0, sizeof(flag));
m[0][1] = 1;
m[0][4] = 1;
m[1][2] = 1;
m[2][3] = 1;
m[2][6] = 1;
m[4][5] = 1;
m[5][1] = 1;
m[5][6] = 1;
for(int i = 0; i < V; i++){
f(i);
}
reverse(v.begin(), v.end());
for(int i = 0; i < v.size(); i++){
cout << v[i] << endl;
}
6、LCA
最深根を基準として定めたとき、
2つのノードを指定すると、
2つのノードに共通の最短根のノード番号を得る。
0-1-3-4
| |
2 5-6-7
例えば上のグラフで最も深い根をノード0としたとき、
ノード4とノード7のLCA(4,7)は3になる。
グラフは閉路を含むものであってはならない。
速度は初期化にO(n*logn)かかり、1回の検索にO(logn)かかる。
#define MAX_V 55
#define MAX_LOG_V 8
vector<int> G[MAX_V];
int root;
int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];
void ae(int from, int to){
G[from].push_back(to);
G[to].push_back(from);
}
void dfs(int v, int p, int d){
parent[0][v] = p;
depth[v] = d;
for(int i = 0; i < G[v].size(); i++){
if(G[v][i] != p)dfs(G[v][i],v,d+1);
}
}
void init(int V){
dfs(root,-1,0);
for(int k = 0; k+1 < MAX_LOG_V; k++){
for(int v = 0; v < V; v++){
if(parent[k][v] < 0)parent[k+1][v]=-1;
else parent[k+1][v] = parent[k][parent[k][v]];
}
}
}
int lca(int u, int v){
if(depth[u] > depth[v])swap(u,v);
for(int k = 0; k < MAX_LOG_V; k++){
if((depth[v] - depth[u]) >> k & 1){
v = parent[k][v];
}
}
if(u == v)return u;
for(int k = MAX_LOG_V - 1; k >= 0; k--){
if(parent[k][u] != parent[k][v]){
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int from[7] = {0,0,1,3,3,5,6};
int to[7] = {1,2,3,4,5,6,7};
int main(){
LCA::root = 0;
for(int i = 0; i < 7; i++){
LCA::ae(from[i],to[i]);
}
LCA::init(6);
cout << LCA::lca(4,7) << endl;
return 0;
}
7、強連結成分分解
強連結成分分解は閉路の検出をします。
例えば、
0→1→2
↑ ↓
3←4→5
上のようなグラフがあったとします。
このとき 1→2→3→4→1 が閉路になります。
例えば上のグラフについて強連結成分分解を行うと、
得られる結果は
0 != 1 == 2 == 3 == 4 != 5
になります。(0!=5)
これは 0 と 1,2,3,4 と 5 という成分に分解されたことを意味します。
このうち 1,2,3,4 は閉路の構成成分であるとわかります。
この 1,2,3,4 を1つのノードとしてみなすことができます。
するとすべての閉路を除去したDAGになります。
強連結成分分解は閉路の検出やグラフのDAG化などに役立ちます。
vector<int> graph[MAX_V];
vector<int> rev_graph[MAX_V];
bool visited[MAX_V];
int cmp[MAX_V];
vector<int> st;
void dfs(int v){
visited[v] = true;
for(int i=0; i<(int)graph[v].size(); i++){
int u = graph[v][i];
if(!visited[u]){
dfs(u);
}
}
st.push_back(v);
}
void rev_dfs(int v, int cnt){
visited[v] = true;
for(int i=0; i<(int)rev_graph[v].size(); i++){
int u = rev_graph[v][i];
if(!visited[u]){
rev_dfs(u, cnt);
}
}
cmp[v] = cnt;
}
void scc(){
memset(visited, 0, sizeof(visited));
memset(cmp, 0, sizeof(cmp));
st.clear();
for(int i=0; i<MAX_V; i++){
if(!visited[i]){
dfs(i);
}
}
memset(visited, 0, sizeof(visited));
int cnt = 0;
while(!st.empty()){
int v = st.back();
st.pop_back();
if(!visited[v]){
rev_dfs(v, cnt++);
}
}
}
int from[5] = {0,1,2,3,3};
int to[5] = {1,2,3,1,4};
int main(){
for(int i = 0, i < 5; i++){
graph[from[i]].pb(to[i]);
rev_graph[to[i]].pb(from[i]);
}
SCC::scc(); // 強連結成分分解
for(int i = 0, i < 5; i++){
cout << cmp[i] << endl;
}
return 0;
}
8、2-SAT
「Aであること」をAとし、「Aで無いこと」を!Aと表記する。
Aが真であれば!Aは偽である。
もしくは、Aが偽であれば!Aは真である。
AもしくはBが真である条件をいくつか列挙する。
例えば、
「AもしくはBが真」
「CもしくはDが真」
などがそうです。
列挙した条件すべてが真であるとしたときに、
その状況があり得るかどうかを判定するのが2-SATです。
つまり、「AもしくはBが真」かつ「CもしくはDが真」です。
例えば、「AもしくはBが真」であれば、
「!AならばB」と「!BならばA」の2つの条件が発生します。
これを!A→Bと!B→Aとしてグラフにできます。
このようにグラフを作っていったときに、
もし「A→!B→!A→B→A」のような部分があってはいけません。
なぜならAと!Bは同時に真もしくは偽にならないからです。
このような場合があればあり得ないと判定します。
この判定はグラフさえ書ければ簡単に判定できます。
強連結成分分解して同じ閉路内にAと!Aが存在しなければ良いのです。