Cにグラフ構造で特定のノードを検索するには？

Question

私は結論に到達し、学校のプロジェクトの1（3の）相が24時間であるので、私のコードを適応させるために、適切にこれを議論する時間を持っていますが、少なくとも私は正しい決断をしたかどうかを知る必要はありませいること。

私はリンクリストを使用して、ここに私の構造だよ。

typedef struct sCity {
    int cityID;
    char *cityName;

    struct sCityLink *links;
    struct sCity *next;
} nCity, *City;

typedef struct sCityLink {
    City cityLinkParent;
    City cityLinkTo;

    struct sCityLink *next;

} nCityLink, *CityLink;

基本的に、私は都市の多くを持っており、それらの都市は、グラフのように、すべて一緒にリンクされています。例えば、A、B、C、D及びEそれらは構造のシティの中にこの順番で挿入されています。次いで、IはB、CとD、BとC、D、E、CとDとEとDとEに接続します。

それでは、私はこれは、リンクリストの最後の一つであり、それは、リンクされたリストのすべての方法を通過するのに時間がかかる都市E.に行く必要としましょう。たぶん5つの都市ではなく、実際のアプリで、この例で私は、少なくとも10,000個の都市のようにサポートすることになっていません。しかし、最短ルートは（出発点である）AからCからEに（またはそれが-D-EまたはA-B-Eとすることができる、重要ではありません）。

私の構造は私が1で全体のリンクリスト1を横断することなく、Eまでの最短ルートを見つけることができますか？そうでない場合は、私が間違ってやってる？

はい、私はそれをどのように行うことができますか？私は、このようなパスを見つけることができる方法の手掛かりを持っていない...

Answer 1

二つの別々の問題があります - 1は、おそらく街のID（例えば「E」）のための市のポインタを見つけたいです。あなたの構造の線形時間未満でそれを行うことはできません。あなたがより速く、それが必要な場合は、ハッシュテーブルまたはバイナリ検索ツリーを使用します。

二つは、次の2つの与えられた都市間のパスを見つけたいです。このために、あなたはおそらくあなたのデータ構造がうまくなるために、BFSアルゴリズムを使用すると思います。 BFSは、VおよびE頂点距離開始頂点から開始から終了頂点までの距離よりも大きくない誘導された部分グラフの頂点及びエッジカウントであるO（V + E）の時間を要することに留意されたいです。最悪の場合を意味し、それは都市のリストを横断するよりも時間がかかります。

Answer 2

あなたは幅優先探索する（BFS）と呼ばれるアルゴリズムを使用することができます。あなたはそれを使用する各ノード上で「色」フラグを実装する必要があります。ご縁がを重み付けされていないのある場合は、このアルゴリズムは唯一機能することに注意してください - 2つの都市が接続されている場合、それらは同じ距離です。 エッジが（彼らは同じように見えていません）重量を持っている場合は、ダイクストラのアルゴリズムのようなものが必要のか、ます。