深さ優先探索で順列列挙(ABC 054 C問題)

今回は無向グラフの問題を題材に深さ優先探索(Depth First Search)を勉強します。
AtCoder Begginer Contest 054のC問題です。問題文の概要は、

「N頂点の無向グラフが与えられたとき、頂点1を始点として全頂点を一度だけ通るパスは何通りあるか」

というものです。

本問ではN≦8なので、頂点1を始点とした順列をすべて列挙しても7!=5040通りとなり、これらの順列についてパスが有効か（各頂点が辺で接続されているか）を調べる方法でも十分間に合います。そしてこのような順列を列挙するには、next_permutationという関数を使うと楽らしいのですが、ここでは深さ優先探索を実装してみます。

与えられた無向グラフを表現するには、隣接行列というものを用いると便利です。
下図のような二次元配列を用意して、頂点同士が辺で接続されていればtrueを、そうでなければfalseを入れていきます。今回は重みなしグラフなのでtrueまたはfalseだけですが、重み付きグラフの場合はその重みを各成分に代入すればOKです。(例えば頂点iから頂点jにコストwの辺が伸びている場合は、(i, j)成分=wとします。)


さて、頂点の接続関係を実装出来たら、頂点1からスタートして遷移できなくなるまで辺で結ばれた頂点へ移っていき、遷移できなくなったら一つ前の状態に戻る、という手法(深さ優先探索)で有効なパスを探していきます。コードはこんな感じになります。

1. 
   

1. const int nmax = 8;
2. //接続状況を格納する隣接行列
3. bool graph[nmax][nmax];
4.  
5. //パスを全探索する関数
6. // v:今いる頂点
7. // N:頂点の数
8. int dfs(int v, int N, bool visited[nmax]) {
9. //すべての頂点に訪れたかどうかのフラグ
10. bool all_visited = true;
11. //一つでも訪れていない頂点があればfalseにする
12. for (int i = 0; i < N; i++) {
13. if (visited[i] == false)all_visited = false;
14. }
15.  
16. //すべての頂点に訪れていれば有効なパスなので1を返す
17. if (all_visited) {
18. return 1;
19. }
20.  
21. int ret = 0;
22.  
23. //すべての遷移先について調べる
24. for (int i = 0; i < N; i++) {
25. //頂点iが接続されていない、あるいはすでに訪れていればi+1に移る
26. if (graph[v][i] == false)continue;
27. if (visited[i])continue;
28. //iに遷移する
29. visited[i] = true;
30. //iからの遷移を試す
31. ret += dfs(i, N, visited);
32. //iのフラグを取り消す
33. visited[i] = false;
34. }
35. return ret;
36. }
37.  
38. int main() {
39. int N, M;
40. cin >> N >> M;
41. for (int i = 0; i < M; i++) {
42. int A, B;
43. cin >> A >> B;
44. //接続状況の入力
45. //無向グラフなので両方向からの接続をtrueにする
46. graph[A - 1][B - 1] = graph[B - 1][A - 1] = true;
47. }
48. bool visited[nmax];
49. //visitedをfalseで初期化する
50. for (int i = 0; i < N; i++) {
51. visited[i] = false;
52. }
53.  
54. visited[0] = true;
55. //頂点0から始まるパスの数を出力する
56. cout << dfs(0, N, visited) << endl;
57. return 0;
58. }