深さ優先探索

[MORIRIN]

コード:

#define N 7
#define M 4

enum {S, A, B, C, D, E, F, G};

int adjacent[N + 1][M] = {
  {S},
  {B, C, S},
  {A, C, D, S},
  {A, B, E, S},
  {B, E, F, S},
  {C, D, G, S},
  {D, S},
  {E, S},
};

質問があります。終端 S も含めると隣接リストの長さは最大で 4 になります。これをマクロ M で定義しています。したがって、大きさは (N + 1) * M になります。と書いてあるのですが、大きさが上記のようになる理由がわかりません。どういうことか教えていただけると助かります。

[asd]

コード:

#define N 7
#define M 4

enum {S, A, B, C, D, E, F, G};

int adjacent[N + 1][M] = {
  {S},
  {B, C, S},
  {A, C, D, S},
  {A, B, E, S},
  {B, E, F, S},
  {C, D, G, S},
  {D, S},
  {E, S},
};

質問があります。終端 S も含めると隣接リストの長さは最大で 4 になります。これをマクロ M で定義しています。したがって、大きさは (N + 1) * M になります。と書いてあるのですが、大きさが上記のようになる理由がわかりません。どういうことか教えていただけると助かります。

いきなりこのプログラムだけを載せられても回答できるかたは少ないかと思います。
見たところ下記のページに掲載されているプログラムを抜き出したものでしょうか？

お気楽Ｃ言語プログラミング超入門－経路探索
http://www.geocities.jp/m_hiroi/linux/clang16.html

引用元がある場合はURLや書籍名等を一緒に書いておいたほうがより回答が付きやすくなるかと思います。

上記で正しいものとして進めますが、上記のプログラム以外の部分にあたる内容について
どこまで理解されているのでしょうか？

そして今回の質問では大きさが(N+1) * Mになる理由が分からないとのことですが、
Nに+1している理由が分からないのでしょうか？

それなりに一通り説明してみます。
今回は上記のページでも説明されている通り、A～Gの7つの頂点があるグラフを例にとり、
その各頂点から接続している頂点を列挙する隣接リストを定義しています。

頂点の数は7つなので頂点同士の隣接有無を行列にして表現する場合7*7(縦と横にA～Gを並べ、隣接する場合は行列の交点を1にするため)の
大きさが必要ですが、隣接する頂点を列挙する方式の場合は上記の例のグラフでは隣接する頂点が最大になるのが、
頂点B,C,D,Eでその数は3個ずつになっています。

B => (A, C, D)
C => (A, B, E)
D => (B, E, F)
E => (C, D, G)

なのでリストの終端Sを考えなければ頂点の数*隣接する頂点の最大数、つまり7*3の大きさがあれば十分足りることになります。

ところが各頂点毎に隣接する頂点の個数が可変なのでリストの終端にSを追加することにしました。
先ほどの隣接リストの末尾に終端Sを追加すると、隣接する頂点の最大数は1つ増えて3+1=4になります。
ここで頂点の数をN、終端も含めた隣接リストの最大個数をMとして表現すると、必要な隣接リストの大きさは
N * Mで表すことができます。

隣接リストは配列で表現することにしましたが終端Sを0として利用することにしたため、
配列adjacent[0]は終端のみを格納しダミー行として使うことにしました。
このダミー行が増えたため、Nに1加えて隣接リストの大きさは(N+1) * Mになりました。

長くなりましたがわからない部分があれば遠慮なく聞いてくださいね。

あと関連する質問についてリンクを貼っておきます。

勉強サイトについて
http://dixq.net/forum/viewtopic.php?f=3&t=17903

幅優先探索
http://dixq.net/forum/viewtopic.php?f=3&t=17906