0

学校のプロジェクトのフェーズ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は、この順序で構造Cityに挿入されます。次に、AをB、CとD、BをC、D、E、CをD、EとDをEに接続します。

ここで、E市に行く必要があるとしましょう。これはリンクリストの最後の都市であり、リンクリストを最後まで通過するには時間がかかります。たぶん、この例では5つの都市ではありませんが、実際のアプリでは、少なくとも10,000の都市のようにサポートすることになっています。ただし、最短ルートはA（開始点）からCからE（またはADEまたはABEの場合もあります）です。

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

はいの場合、どうすればそれを行うことができますか？どうすればそのような道を見つけることができるのか分かりません...

4

2 に答える 2

1

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

于 2009-03-22T00:27:04.937 に答える
1

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

2つ目は、指定された2つの都市間のパスを見つけたいということです。このためには、おそらくデータ構造が適切なBFSアルゴリズムを使用します。BFSにはO（V + E）時間がかかることに注意してください。ここで、VとEは、開始頂点からの頂点の距離が開始頂点から終了頂点までの距離よりも大きくない誘導部分グラフの頂点とエッジの数です。つまり、最悪の場合、都市のリストをトラバースするよりも時間がかかります。

于 2009-03-22T00:29:49.030 に答える