3

私は教科書Introduction to Algorithms別名を読んでいます、私はcで使用アルゴリズムCLRSを実装したいです、私が知りたいのは、どのグラフ実装を使用すべきか、隣接リストまたは隣接行列ですか？隣接リストを使用するときにソートするのは直感的ではないと思います。隣接リストの表現は、次のように隣接リストを定義するときに混乱します。mstkruskaledgesedge

typedef struct tagAdjList
{
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

エッジをソートするとき、上で定義されたノードを指すためのポインターの配列を使用したいのですが、問題は、上で定義された構造体がstart pointエッジのを見つけることができないということend pointです。だから私はこのように構造体を変更しました：

typedef struct tagAdjList
{
    int startPointIndex;
    int endPointIndex;
    struct tagAdjList * next;
}AdjNode, *AdjList, *AdjPNode;

私が聞きたいのは、次のように隣接リストを定義しても大丈夫ですか？またはより良い練習がありますか？または、隣接行列を使用する必要があります（インターネットを検索するときに行列を使用してクラスカルを実装する人がいるのを見たので）？なぜ？英語が下手でごめんなさい。どんな助けでもありがたいです。

4

2 に答える 2

3

クラスカルのアルゴリズムを実装する目的では、頂点に属するエッジを並べ替えることはないため、グラフをどのように表現するかは重要ではありません。むしろ、すべてのエッジを1つの配列に配置してから、その配列を昇順で並べ替えます。

グラフを歩くことができ、すべてのエッジを1つの配列に集めることができる限り、グラフの表現は重要ではありません（最初にグラフを歩いてエッジを数え、次に十分な容量の配列を割り当て、最後にグラフを再度作成し、エッジへのポインタを動的に割り当てられた配列に配置します）。

エッジへのポインタが配列に含まれるようになったら、配列を並べ替えて（たとえば、を使用してqsort）、クラスカルのアルゴリズムを実行します。フォレストを効率的にマージするには、互いに素なセットを実装する必要があります。リンクリストの実装に問題がない限り、互いに素なセットを実装してもまったく問題はありません。

于 2012-12-22T04:01:41.043 に答える
0

あなたが言及する最初の構造は、（まばらな）グラフの標準的な表現です。ウェイトフィールドも必要になることに注意してください。少なくともスパースである限り、これをグラフの永続的な表現として保持します。

はい、クラスカルの場合、明示的なソース頂点が必要なため、後者のような構造が必要になります。クラスカル法のためだけにリンクリストを持たない別の構造を定義します。

int startPointIndex;
int endPointIndex;
int weight;

これらの構造の配列を割り当て、グラフのエッジで塗りつぶし、重みで並べ替えてから、端点の互いに素な集合和集合を実行してそれらをスキャンします。

于 2012-12-23T22:40:22.990 に答える