グラフアルゴリズムのライブラリ[1]

グリッド

グリッド上のBFS(最短経路)

//各点のスタートからの距離を配列で返す
//si,sj:スタートの座標
//スタートは壁ではない
//辿り着けない:-1
vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) {
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> d(h, vector<int>(w, INF));
	d[si][sj] = 0;
	queue<pair<int,int>> que;
	que.push(pair<int,int>(si, sj));
	while (!que.empty()) {
		pair<int,int> pos = que.front();
		que.pop();
		int i = pos.first, j = pos.second;
		for (int k = 0; k < 4; k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (ni < 0 || ni >= h) continue;
			if (nj < 0 || nj >= w) continue;
			if (field[ni][nj] == '#') continue;
			if (d[ni][nj] > d[i][j] + 1) {
				d[ni][nj] = d[i][j] + 1;
				que.push(pair<int,int>(ni, nj));
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (d[i][j] == INF) {
				d[i][j] = -1;
			}
		}
	}
	return d;
}

コード例

//各点のスタートからの距離を配列で返す
//si,sj:スタートの座標
//スタートは壁ではない
//辿り着けない:-1
vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) {
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> d(h, vector<int>(w, INF));
	d[si][sj] = 0;
	queue<pair<int,int>> que;
	que.push(pair<int,int>(si, sj));
	while (!que.empty()) {
		pair<int,int> pos = que.front();
		que.pop();
		int i = pos.first, j = pos.second;
		for (int k = 0; k < 4; k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (ni < 0 || ni >= h) continue;
			if (nj < 0 || nj >= w) continue;
			if (field[ni][nj] == '#') continue;
			if (d[ni][nj] > d[i][j] + 1) {
				d[ni][nj] = d[i][j] + 1;
				que.push(pair<int,int>(ni, nj));
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (d[i][j] == INF) {
				d[i][j] = -1;
			}
		}
	}
	return d;
}

void print_vector(vector<vector<int>>V) {
	rep(i, V.size()) {
		rep(j, V[i].size()) {
			cout << V[i][j];
			if (j == V[i].size() - 1) {
				cout << endl;
			}
			else {
				cout << ' ';
			}
		}
	}
}

signed main() {
	int h, w;
	cin >> h >> w;
	int si, sj;
	cin >> si >> sj;
	vector<vector<char>>field(h, vector<char>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> field[i][j];
		}
	}
	vector<vector<int>>d = bfs_grid_pass(si, sj, field);
	print_vector(d);
}

入力
7 8
1 1
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

出力
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 1 2 3 4 5 -1
-1 1 -1 -1 -1 -1 -1 -1
-1 2 3 -1 11 10 11 -1
-1 3 4 -1 -1 9 10 -1
-1 -1 5 6 7 8 9 -1
-1 -1 -1 -1 -1 -1 -1 -1

グリッド上のBFS(色分け)

//0から始まる数字で色分けする
//壁:-1
vector<vector<int>>bfs_grid_color(vector<vector<char>>field) {
	int color = 0;
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> COLOR(h, vector<int>(w, INF));
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	rep(si, h) {
		rep(sj, w) {
			if (field[si][sj] != '#') {
				if(COLOR[si][sj]==INF){
				COLOR[si][sj] = color;
				queue<pair<int, int>> que;
				que.push(pair<int, int>(si, sj));
				while (!que.empty()) {
					pair<int, int> pos = que.front();
					que.pop();
					int i = pos.first, j = pos.second;
					for (int k = 0; k < 4; k++) {
						int ni = i + di[k], nj = j + dj[k];
						if (ni < 0 || ni >= h) continue;
						if (nj < 0 || nj >= w) continue;
						if (field[ni][nj] == '#') continue;
						if (COLOR[ni][nj] > COLOR[i][j] + 1) {
							COLOR[ni][nj] = color;
							que.push(pair<int, int>(ni, nj));
						}
					}
				}
				color++;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (COLOR[i][j] == INF) {
				COLOR[i][j] = -1;
			}
		}
	}
	return COLOR;
}

コード例

//0から始まる数字で色分けする
//壁:-1
vector<vector<int>>bfs_grid_color(vector<vector<char>>field) {
	int color = 0;
	int h = field.size();
	int w = field[0].size();
	vector<vector<int>> COLOR(h, vector<int>(w, INF));
	vector<int>di;
	di = { 0,1,0,-1 };
	vector<int>dj;
	dj = { 1,0,-1,0 };
	rep(si, h) {
		rep(sj, w) {
			if (field[si][sj] != '#') {
				if(COLOR[si][sj]==INF){
				COLOR[si][sj] = color;
				queue<pair<int, int>> que;
				que.push(pair<int, int>(si, sj));
				while (!que.empty()) {
					pair<int, int> pos = que.front();
					que.pop();
					int i = pos.first, j = pos.second;
					for (int k = 0; k < 4; k++) {
						int ni = i + di[k], nj = j + dj[k];
						if (ni < 0 || ni >= h) continue;
						if (nj < 0 || nj >= w) continue;
						if (field[ni][nj] == '#') continue;
						if (COLOR[ni][nj] > COLOR[i][j] + 1) {
							COLOR[ni][nj] = color;
							que.push(pair<int, int>(ni, nj));
						}
					}
				}
				color++;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (COLOR[i][j] == INF) {
				COLOR[i][j] = -1;
			}
		}
	}
	return COLOR;
}

void print_vector(vector<vector<int>>V) {
	rep(i, V.size()) {
		rep(j, V[i].size()) {
			cout << V[i][j];
			if (j == V[i].size() - 1) {
				cout << endl;
			}
			else {
				cout << ' ';
			}
		}
	}
}

signed main() {
	int h, w;
	cin >> h >> w;
	vector<vector<char>>field(h, vector<char>(w));
	rep(i, h) {
		rep(j, w) {
			cin >> field[i][j];
		}
	}
	vector<vector<int>>COLOR(h, vector<int>(w));
	COLOR = bfs_grid_color(field);
	print_vector(COLOR);
}

入力
4 4
..#.
..#.
.#..
.#..
出力
0 0 -1 1
0 0 -1 1
0 -1 1 1
0 -1 1 1

グラフ

これ以降は隣接リストを使う
以前の記事で隣接リストに二次元vectorを使ったがsetを使った方が便利なので変える
※補足
隣接リストの作り方(重みなしグラフ)
setのvectorにする。

a bと入力されるとする
これは頂点aと頂点bが繋がっているということである。

コード

signed main() {
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}

	rep(i, V) {
		for (auto x : G[i]) {
			cout << x << ' ';
		}
		cout << endl;
	}

}

入力
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
3
2 3
1
0 1 4 7
3 7
6
5
3 4

BFS(最短経路)

//スタートからの距離を配列で返す
//start:スタートの頂点番号
//辿り着けない:-1
vector<int>bfs_graph_pass(int start, vector<set<int>>G) {
	int V = G.size();
	vector<int>dist(V, INF);
	queue<int> que;
	dist[start] = 0;
	que.push(start);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (auto nv : G[v]) {
			if (dist[nv] != INF)continue;
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
	rep(i, V) {
		if (dist[i] == INF) {
			dist[i] = -1;
		}
	}
	return dist;
}

コード例

//スタートからの距離を配列で返す
//start:スタートの頂点番号
//辿り着けない:-1
vector<int>bfs_graph_pass(int start, vector<set<int>>G) {
	int V = G.size();
	vector<int>dist(V, INF);
	queue<int> que;
	dist[start] = 0;
	que.push(start);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (auto nv : G[v]) {
			if (dist[nv] != INF)continue;
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
	rep(i, V) {
		if (dist[i] == INF) {
			dist[i] = -1;
		}
	}
	return dist;
}


signed main() {
	int start;
	cin >> start;
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}

	vector<int>dist = bfs_graph_pass(start, G);
	rep(i, V) {
		cout << dist[i] << ' ';
	}

}

入力
0
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
0 2 3 1 2 -1 -1 2

BFS(色分け)

0から始まる数字で連結成分ごとに色分けする。

//0から始まる数字で色分けして配列で返す
vector<int>bfs_graph_color(vector<set<int>>G) {
	int color = 0;
	int V = G.size();
	vector<int>COLOR(V, INF);
	rep(start, V) {
		if (COLOR[start] == INF) {
			queue<int> que;
			COLOR[start] = color;
			que.push(start);
			while (!que.empty()) {
				int v = que.front();
				que.pop();
				for (auto nv : G[v]) {
					if (COLOR[nv] != INF)continue;
					COLOR[nv] = color;
					que.push(nv);
				}
			}
			color++;
		}
	}
	return COLOR;
}

コード例

//0から始まる数字で色分けして配列で返す
vector<int>bfs_graph_color(vector<set<int>>G) {
	int color = 0;
	int V = G.size();
	vector<int>COLOR(V, INF);
	rep(start, V) {
		if (COLOR[start] == INF) {
			queue<int> que;
			COLOR[start] = color;
			que.push(start);
			while (!que.empty()) {
				int v = que.front();
				que.pop();
				for (auto nv : G[v]) {
					if (COLOR[nv] != INF)continue;
					COLOR[nv] = color;
					que.push(nv);
				}
			}
			color++;
		}
	}
	return COLOR;
}


signed main() {
	int V;//頂点数
	int E;//辺の数
	cin >> V >> E;
	vector<set<int>>G(V);//隣接リスト
	for (int i = 0; i < E; i++) {
		int a, b;
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
	}
	vector<int>COLOR = bfs_graph_color(G);
	rep(i, V) {
		cout << COLOR[i] << ' ';
	}
}

入力
8 7
0 3
1 3
1 2
3 7
3 4
7 4
5 6

出力
0 0 0 0 0 1 1 0