1

ノードの束と、特定のノード間の重みを持つエッジを取り込まなければならないプロジェクトが割り当てられました。

次に、この情報を使用して、グラフの各連結コンポーネントの最小スパニング ツリーを見つける必要があります (したがって、グラフに 2 つの連結コンポーネントがある場合は、2 つのスパニング ツリーを作成する必要があります)。

キャッチは、を除くSTLライブラリを使用できないことです。

独自のデータ構造を作成する必要があることはわかっていますが、どのデータ構造が必要になるかわかりません。最小ヒープは、使用する最小の重みのエッジを見つけるのに役立つと思いますが、接続されたコンポーネントごとに最小ヒープを作成するにはどうすればよいですか?

そして、接続されたコンポーネントのセットを整理するために、union-find を実装する必要があると考えていました。

これには他にどのようなデータ構造を実装する必要がありますか?

4

2 に答える 2

1

MST アルゴリズムを選択でき、出力はエッジのリストであると仮定します。Borůvka のアルゴリズムは実装が簡単で、グラフと互いに素な集合構造以外のデータ構造は必要ありません。対照的に、Prim のアルゴリズムには優先キューと切断されたグラフを処理するロジックが必要であり、Kruskal のアルゴリズムには互いに素な集合構造と並べ替えアルゴリズムが必要です。このようなデータ構造を設定します。インシデントの頂点とエッジのペアごとに隣接レコードがあります。

struct Adjacency;

struct Edge {
    int weight;
};

struct Vertex {
    struct Adjacency *listhead;  // singly-linked list of adjacencies
    struct Vertex *parent;  // union-find parent
};

struct Adjacency {
    struct Adjacency *listnext;
    struct Edge *edge;
    struct Vertex *endpoint;  // the "other" endpoint
};
于 2013-07-17T00:26:19.210 に答える