C：経路検索アルゴリズム

全経路検索について勉強中です。

「各ノードはポインタで繋がっている」という事は理解しましたが、それをどのように表せば良いのでしょう。
ダイクストラ法、深さ優先検索等の単語は見つかりましたが、どれを使用すれば良いのか…。

条件は、ノードの数は決まっておらず、つながり・出発,到着点は自由に決める事が出来ます。
　例）1-2 1-4 2-4 2-3 3-5 4-5 開始,3 到着,5
距離は関係ありません。

今はリスト構造で、構造体（下のようにしています）は動的に確保し、
再帰で処理をするようにしていますが、上手くいかず不安になってきました。

struct data{
　　int x;　　　　　　　/*ノード*/
　　struct data *next; /*次ノードへのつながり*/
};

よろしければ、何か些細な事でもヒントを下さると嬉しいです＾＾

No.3 回答者： N-iml 回答日時： 2008/07/01 13:33

投稿者です。

nimlのアカウント紛失…orz の為、こちらから失礼致します。
折角ご回答下さったのに、ポイント等付けれずに申し訳無いです。


No.1 Tacosan さん
　プログラムにおいての表現、ですか。
　その事を考えずに（思いつかず）、何を使おうかと焦っていました。
　
　隣接リストで表現し、トラックバックなるものを使用して検索するのですね。
　本なりネットを参考に頑張りますっ。

　物事の考え方―何をすべきかを、最初に考えなければならないですね。
　考える為には、把握しないと駄目なのかな。
　何となく、思考の弱点がわかったような気がしました。
　　

No.2 JaritenCat さん
　ノード管理のリストと接続先管理のリストを、ですか。
　Tacosanさんにアドバイス頂いた隣接リストをネットで調べ、現在下記のようになりましたが…間違いのようですね；
　書いて下さったプログラムを研究して、考え直してみます。

　struct data{
　　　int x;　/*ノード*/
　　　struct connect *list;　/*つながり先のリスト*/
　};
　struct connect{
　　　int y;　/*つながり先の頂点*/
　　　struct connect *next;　/*次リスト*/　
　};
　

　お二人のアドバイスで、すべき事が見えた気がします。
　ありがとうございました＾＾

No.2 回答者： JaritenCat 回答日時： 2008/06/29 02:53

ノード数が不定ですのでノードのリストを作るところはＯＫです。

ノードとノードのつながりをどう管理するかが問題ですが、接続先のリストも作ってはどうでしょう。

struct data { /* ノードを管理するリスト */
int x; /* ノード名 */
struct data *next; /* 次のノード */
　struct path *list; /* 経路リストへのポインタ */
}
struct path { /* 接続先を管理するリスト */
　struct path *next; /* 接続先 */
}

No.1 回答者： Tacosan 回答日時： 2008/06/26 12:54

とりあえず, 「プログラムにおいてグラフをどのように表現するか」を考えないとダメだねぇ.

プログラム上は隣接行列でも隣接リストでも表現できるけど, 全経路探索するなら隣接リストで表現するのかなぁ.
で, 全経路探索ということだと結局はバックトラックすることになるんだけど, この辺は OK?