【グラフ理論】深さ優先探索の雛形コードを書く

##記事背景##
　AtCoder初心者のrib7です。atcoderで高成績を狙うには、ある程度コードのストックを持っておくことが大切だと思います。そこで今回は、グラフ理論における幅優先探索(以降BFS)の計算コード雛形を作成し、実際の問題への使い方を解説していきます。

##グラフ理論におけるBFSの概要##
　グラフ理論とは何なのか、BFSとは何なのか、についてはネットで検索すればいくらでも記事があるのでそちらを参考にしてください。AtCoderにおけるグラフ理論は大体「街とそれらを結ぶ道が出てくる」ことが多く一目でわかることが多いです。（グラフ理論の適用範囲は広いのでそれ以外の問題も出るかもしれません~~がどうせそんな問題は皆できないからええやろ~~。）なので前回の記事[【atcoder】二分探索問題をマスターする][link-1]で取り上げた二分探索よりは使うタイミングが分かりやすく対策が立てやすい一方、「知らなきゃ絶対解けない」のが特徴として挙げられます。だからこそ、知識と練習が必要になります。ちなみにどちらもABCのD問題において頻出です。
[link-1]:https://qiita.com/drafts/fa3ef8b8abbef3eae9a4/edit

##グラフ理論におけるBFSのコード##
 さて今回も雛形を作っていきましょう。グラフ理論で幅優先探索と深さ優先探索のどちらがいいのかについてはタイミングにもよると思うのですが、どんな問題でもどちらかでしか絶対解けないということはない(と思う)のでとにかく幅優先探索のコードを改変したり付け足したりして問題を解いていきます。今回のプログラムコードは原理のみを実装してみました。内容は次の通りです。大切なのは関数bfs()です！！

① まずmain()の中でA, B, C, MAPベクトルの整備を行います。道iに対してA[i]は出発都市、B[i]は到着都市、C[i]は道の長さです。MAP[i][j]は都市iから都市jまでの最短経路を通った時の最短必要時間が格納される予定のベクトルです。
② 次に出発都市をsとして関数anl_bfs(s)を呼び出します。これで先ほど用意したMAPに最短必要時間が格納されます。これでほとんどの問題は解けてしまいますね！！
③ 今回は、任意の都市から任意の都市に行くのにかかる時間を全て足してみました。ここは問題によって変化させます。


```c++:graph_bfs.cpp
#include <iostream>
#include<vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<vector<pair<int, int>>> G(1);
vector<int> A(1), B(1), C(1);
vector<vector<int>> MAP(1, vector<int>(1));
int N, M;

void anl_bfs(int n) {
	//都市nから任意の都市sへの最短経路を深さ優先探索によってMAP[n][s]に格納
	MAP[n][n] = 0;
	queue<int> que;
	vector<int> t(N);
	que.push(n);
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		int cost, dist;
		for (int i = 0; i < G[x].size(); i++) {
			cost = C[G[x][i].second];
			dist = G[x][i].first;
			que.push(dist);
			if (MAP[n][dist] == -1)MAP[n][dist] = MAP[n][x] + cost;
			else {
				if (MAP[n][dist] > (MAP[n][x] + cost))MAP[n][dist] = MAP[n][x] + cost;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (MAP[n][i] <= 0)MAP[n][i] = 0;
	}
}

int main() {
	cin >> N >> M;
	long long sum = 0;
	G.resize(N + 1); A.resize(M); B.resize(M); C.resize(M); MAP.resize(N + 1, vector<int>(N + 1, -1));
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i] >> C[i];
		G[A[i]].push_back(make_pair(B[i], i));
	}
	for (int i = 1; i < N + 1; i++) {
		anl_bfs(i);
		for (int j = 1; j < N + 1; j++) {
			sum += MAP[i][j];
		}
	}
	cout << sum;
}
```

##実際の問題への適用##
　さて上記のプログラムコードの雛形を実際に使ってみましょう。今回適用してみる問題は競プロ典型90問の3問目である[003 - Longest Circular Road（★4）][link-2]です。今回の雛形コードと異なる点は下記の通りです。
>
① 道が双方向でループしてしまう
② 道の長さや所要時間が書いていない
③ 最短経路問題を解いた後が大変(スコアの導入が必要)

なので下記の対策を講じてコードを書き替えてみます。
>
① ベクトルDを導入(一度通った都市を1、通っていない都市を-1とすることでループを防止する)
② 道の長さは等しく1にする
③ 都市1から最も遠い都市Aを選び、都市Aから最も遠い都市Bを選べばA-Bが最も遠い都市である。その２都市をつなぐ道が答えとなる。(詳しくは[公式解説：木の直径は最短経路計算を２回やる][link-3])
※また、実際に提出してみるとメモリオーバーとなったのでMAPの初期化を限定しました。

解答は下記のようになりました。(回答提出がACされるのは確認済)

[link-2]:https://atcoder.jp/contests/typical90/tasks/typical90_c
[link-3]:https://github.com/E869120/kyopro_educational_90/blob/main/editorial/003.jpg

<details><summary>解答(クリック)</summary><div>

```c++:graph_bfs_2.cpp
#include <iostream>
#include<vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<vector<pair<int, int>>> G(1);
vector<int> A(1), B(1), C(1), D(1);
vector<vector<int>> MAP(1, vector<int>(1));
int N, M;


void anl_bfs(int n) {
	//都市nから任意の都市sへの最短経路を深さ優先探索によってMAP[n][s]に格納
	MAP[n][n] = 0;
	queue<int> que;
	vector<int> t(N);
	que.push(n);
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		if (D[x] != -1) { continue; }
		else { D[x] = 1; }
		int cost, dist;
		for (int i = 0; i < G[x].size(); i++) {
			cost = C[G[x][i].second];
			dist = G[x][i].first;
			que.push(dist);
			if (MAP[n][dist] == -1)MAP[n][dist] = MAP[n][x] + cost;
			else {
				if (MAP[n][dist] > (MAP[n][x] + cost))MAP[n][dist] = MAP[n][x] + cost;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (MAP[n][i] <= 0)MAP[n][i] = 0;
	}
}

int main() {
	cin >> N;
	M = N - 1;
	long long sum = 0;
	G.resize(N + 1); A.resize(M); B.resize(M); C.resize(M); 
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i];
		C[i] = 1;
		G[A[i]].push_back(make_pair(B[i], i));
		G[B[i]].push_back(make_pair(A[i], i));
	}

	MAP.resize(N + 1, vector<int>(1));
	MAP[1] = vector<int>(N+1,-1);
	D.resize(N + 1, -1);
	anl_bfs(1);
	int score = 0, king = 0, king_city = 0, queen = 0, queen_city = 0;
	for (int i = 0; i < N + 1; i++) {
		score = MAP[1][i];
		if (score > king) { king = score; king_city = i; }
	}

	D = vector<int>(N + 1, -1);
	MAP[king_city] = vector<int>(N + 1, -1);
	anl_bfs(king_city);
	for (int i = 0; i < N + 1; i++) {
		score = MAP[king_city][i];
		if (score > queen) { queen = score; queen_city = i; }
	}

	cout << queen + 1;
}
```
</div></details>

　このように、先ほどの雛形からほとんど変更せずに問題を解く事ができます。雛形を使うことで少し変なコードになりますし、どうしても長くなってしまうというデメリットはあるのですが、まずは正解することから始めてみましょう。少しずつコードを改変することでどうなっているのか理解できますし、１から書くより効率的です。コードの改変のポイントはベクトルGの役割(G[i]は都市iから続く行き先リスト)を理解する事です。

#まとめ#
　いかがだったでしょうか。グラフ理論の最短経路問題はABC頻出中の頻出ですが、何となく難しそうという印象で敬遠する人が多いとは思います。しかし、上で作ったような雛形を改変して様々な問題に適用する練習を積んでいけば、グラフ問題を得点源とすることができるでしょう。目指せグラフ理論マスター！！