令和3年度 III-2

解説

この問題で問われていること

隣接行列で表したグラフ上で、単純パス(同じ頂点を2度通らないパス)をすべて列挙するプログラムの条件を補う問題。

解き方

① 経路を進む条件は「辺がある(c==1)」かつ「まだ通っていない(i not in r)」
② orにすると辺のない頂点や通った頂点にも進んでしまう。c==0やi in rは条件が逆
③ ④

正解が正しい理由

隣接行列の行lの各要素cは、現在の頂点から頂点iへ辺があれば1である。辺があること(c==1)と、頂点iがこれまでの経路rに含まれていないこと(i not in r)の両方が必要で、(c==1) and (i not in r)となる。これにより閉路を避けながら再帰的に探索でき、実行結果の[0,1,2,3]、[0,1,3]、[0,2,1,3]、[0,2,3]の4経路が得られる。したがって④が正しい。

この問題で必要な基礎

■ プログラムの読み方
・mm[i]は隣接行列のi行目で、頂点iから各頂点へ辺があるか(1)ないか(0)を表します。
・「for i, c in enumerate(l)」は、行lの要素を先頭から順に見ていき、そのときの位置(頂点番号)をi、値(0か1)をcとして繰り返す、という意味です。
・rはここまでたどってきた頂点の並び(経路)です。「i not in r」は「頂点iがまだ経路に入っていない」、「i in r」は「すでに入っている」という意味です。
・andは「両方とも成り立つ」、orは「どちらか一方でも成り立つ」を表します。

各選択肢について

• ① (c==1) or (i not in r)では、辺がなくても未訪問なら進んでしまい、隣接していない頂点にも遷移してしまう。
• ② (c==0) and (i in r)では、辺がなく、かつ訪問済みの頂点に進む条件になり、意図と逆である。
• ③ (c==0) or (i in r)では、辺がない場合や訪問済みの場合に進むことになり、誤り。
• ④ (c==1) and (i not in r)は、辺があり、かつ未訪問の頂点だけに進む条件で、出力の4経路が得られる。これが正答。
• ⑤ (c==1) or (i in r)では、訪問済みの頂点にも進み、無限再帰や重複経路を生じる。

覚えるべきポイント

グラフの経路探索では、「辺がある」かつ「未訪問である」ことを条件にして進む。訪問済み判定を怠ると、閉路により無限ループする。