すべての木のパス（経路）を求めたいのですが

質問

こんにちは。学校の課題のことで質問させてもらいます。

例えばAはB1,B2,B3,B4に接続されています。B1はC1,C2へ,B2はC3,C4へ,B3はC5,C6へ,B4はC7,C8へそれぞれ接続されています。このような木の経路は８種類で

A→B1→C1
A→B1→C2

　…

A→B4→C7
A→B4→C8

ですよね？これですべての経路を画面に出力するようなプログラムを考えなければならないのですが、どのようにすすめていいか分からないです。AからBなどの接続はポインタによって接続されています。

コンピュータにポインタを辿らせると最初のA→B1→C1の経路しか選択しないので一度通った場所（ノード？）には通らないように目印を付けなければならないと思うのですが、その条件がよくわからないです。
またこのようなプログラムはfor文やwhile文を使うのではなく再帰呼び出しを使うのでしょうか？
補足質問もわかる範囲ならば答えたいと思います。
回答よろしくお願いします。

回答No.3

noocyte · ベストアンサー

始点を S1，…，S6，終点を E1，E2 として，仮に S1 と E1 を選んだとしましょう．

>（終点が２つなので）自分が選択した終点に辿り着いたものだけを
> 表示させるためにはどうしたらよいのでしょうか？

現在の経路を表示させるか否かを判断できるのは，E1 または E2 に到達した時点です．
それまで，現在の経路を覚えておく必要があります．
(単純に，途中のノードを訪れるたびにその名前を出力していたのでは，
不要な経路も出力されてしまいます．)

経路を N0(＝S1) → N1 → N2 → … → Nm(＝E1 または E2) とします．
多分この課題ではすべての経路についてのｍの最大値 (つまり最長経路の長さ)
はわかっているでしょうから，max(m)＋1 個以上の要素を持つ，ノードへの
ポインタ配列を用意して，そこに現在の経路を記憶させるのが最も簡単でしょう．

S1 を出発点として #1 のトラバース (渡り歩く) プログラムを使って，
E1 に到達するたびに配列に記憶させた経路を出力すれば OK です．
(E2 に到達したときは何もしない．)

もちろん，#1 のプログラムを少し拡張して，上記配列の添字
(＝出発点 S1 から現在位置までの距離) を管理するようにしなければなりません．
あと，各ノードの値の合計も．

＃ ●余談
＃ 実は配列を使わなくても，現在の経路は再帰呼び出しのスタックが覚えており，
＃ そこから情報を取り出すという手もあるのですが，少しプログラムがわかりにくく
＃ なるのでやめときます：）
＃ でも，自分ではこっちの手を使います：）

●参考
以下のキーワードで検索してみるといいかもしれません．

・"アサイクリックグラフ" (acyclic graph) または
"有向非環状グラフ" (directed acyclic graph，"DAG")
(ループのない有向グラフ)

・"深さ優先探索" (depth-first search) または "縦型探索"
(#1 のようなアルゴリズムを一般化したもの．)

・"グラフのトラバース"
(グラフのすべてのノードを順番に渡り歩くこと)

お礼

回答ありがとうございます！！
その経路が求めたい経路かどうかを判断できるのは終点に達した時点だから、通過した場所を記憶するものを用意しておけばよかったんですね。
自分でもどのようなことをすれば良いかイメージができてきました。
試行錯誤してプログラムを作ってみたいと思います！
参考になりました！！

回答No.2

noocyte

私はグラフアルゴリズムが好きなので口出ししちゃいます．(笑)
でも，正解はすでに #1 さんが書いておられるとおりだし，
課題ということなのであまり詳しくは書けないので補足程度に．

> またこのようなプログラムはfor文やwhile文を使うのではなく
> 再帰呼び出しを使うのでしょうか？

#1 さんの回答にあるとおり，
・経路を先に進むには再帰呼び出しを使う．
・枝分かれした道をすべて列挙するには for または while を使う．

> 一度通った場所（ノード？）には通らないように目印を
> 付けなければならないと思うのですが、

この課題は経路にループがない木なので，その必要はありません．

＃ ●余談 (読み飛ばしてもかまいません．)
＃ ループが存在しなくても合流点が存在し，かつそれ以後の経路を
＃ 重複して列挙しないという課題であれば目印をつける必要があります．
＃ しかしこの課題は「すべての経路を列挙せよ」ということなので，
＃ 仮に合流点が存在していたとしても目印は不要です．

お礼

回答ありがとうございました！
参考になりました！！

補足

回答ありがとうございます！！
再帰呼び出しを使うことはわかりました。ただ実はこの課題の木はこのように単純ではなくて、始点が６つで終点が２つあります。自分が選択した始点と終点を結ぶ複数の経路を列挙しなければならないのです。
質問事項に書いていなくてすいません。

さらに通るノードが所持している値を加算して、その複数の経路の中で最も加算した値が小さいものの値と経路を出力しなければなりません。（これは多分自分でもできそうです）

この場合も再帰呼び出しですべての経路を求めることは出来ると思いますが、ゴールが２つあるので自分が求めたい経路を辿らないかもしれません。（終点が２つなので）自分が選択した終点に辿り着いたものだけを表示させるためにはどうしたらよいのでしょうか？printf文を再帰呼び出しの中に書くと不要な経路まで出力されそうです。
長文になり申し訳ありません。お暇であればお答えいただくとありがたいです。
回答参考になりました！！

回答No.1

επιστημη（@episteme）

ループのない"木"であれば、
void 渡り歩く(ノード x) {
　for ( すべての x の子: child に対し ) {
　　渡り歩く(child);
　}
}
↑これを根に対して適用すればいいでしょう。

お礼

回答ありがとうございます！！
再帰呼び出しを使うのですね。
プログラムを書いてみたいと思います。
参考になりました！！