11

方向付けられていないマルチグラフ (速度とメモリが最適化されている) を記述するのに最適なデータ構造は何ですか?

私のコードでは頂点の近傍を取得することが頻繁に発生するため、エッジのリストは不適切です。

訪問したエッジに関する情報を保持する必要があり、1 から 3 のエッジが訪問された場合 (たとえば、1 の近隣をトラバースして、3 につながり、重みを持つエッジを見つけたとしますw)、隣接リストは適切ではありません。 3 の近隣のリストで同じエッジを見つけて、訪問済みとしてマークする必要がありますが、これは遅いです。

各セルが、頂点が訪問されたかどうか、エッジの重みなどに関する情報を表す構造体であるset<Edge>場合、隣接行列について考えました。線形検索なし。Edgegraph[0][1][i]graph[1][0]

マルチグラフを表現する際の適切なアプローチとテクニックはありますか? のような第 3 のライブラリ ソリューションは必要ありませんboost::AdjacencyList。私は自分でそれを書かなければなりません。

編集：誤解して申し訳ありません。これは大学の演習であり、標準ライブラリのみを使用して実行できます。グラフには制約があります: 0 < n ≤ 300 - 頂点の数 0 < m ≤ 20000 - エッジの数 1 ≤ w ≤ 500

メモリ制限は 32 MB、時間制限は 0.5 秒です (DFS でトラバースする必要があります)。

4

1 に答える 1

4

ただし、効率的なローカル操作を提供するやや複雑な表現は次のとおりです。

struct Link;

struct Node
{
    Link *firstIn, *lastIn, *firstOut, *lastOut;
    ... node data ...
};

struct Link
{
    Node *from, *to;
    Link *prevInFrom, *nextInFrom, *prevInTo, *nextInTo;
    ... link data ...
};

基本的に、それぞれNodeに 2 つの二重リンク リストがあり、1 つは着信リンク用で、もう 1 つは発信リンク用です。それぞれLinkが開始と終了Nodeを認識し、それを含む 2 つのリスト ("from" ノードの発信リストと "to" ノードの着信リスト) の前と次のポインターも持っています。

このアプローチを使用すると、どのリンクがノードに到着しているか、どのリンクがノードを離れているかを見つけるためにO(1)、ノードとリンクの作成と破棄を取得できます。この構造は、同じノード ペア間の複数の接続と複数のループもサポートします。O(inbound_deg(node))O(outbound_deg(node))

必要なスペースは、ノードごとおよびリンクごとに固定量ですが、オーバーヘッドは、アプリケーションに応じて問題ない場合もあります (ノードごとに 4 つのポインター、リンクごとに 6 つのポインター)。二重リンク リストの代わりに単純なリストを使用すると、オーバーヘッドはノードごとに 2 つのポインター、リンクごとに 4 つのポインターになりますが、リンクの削除O(outbound_deg(from) + inbound_deg(to))は一定ではなくなります。

また、示されている構造はキャッシュに適していないことに注意してください。また、最近のデスクトップ コンピューターでは、たとえば、二重リンク リストの代わりにポインターのベクトルを使用すると、リストの大きさに応じて速度が向上します。であり、グラフ構造を変更する頻度。

リンクオブジェクトを分割して、たとえば「from」ノードにフォワードリンクデータを埋め込み、「to」ノードにバックポインタを保持することも理にかなっている場合があります。

struct Node
{
    struct OutgoingLink
    {
        Node *to;
        int incoming_index;
        ... link data ...
    };

    struct IncomingLink
    {
        Node *from;
        int outgoing_index;
    };

    std::vector<OutgoingLink> outgoing_links;
    std::vector<IncomingLink> incoming_links;

    ... node data ...
};

ほとんどの場合、リンクを順方向にトラバースし、リンクが既存のノードに追加されていない場合は、ノードと発信リンク データに 1 つのメモリ チャンクを使用するだけでよいのですが、残念ながらこれは簡単ではありません。 C++ でサポートされています。

Cでは、

typedef struct TOutgoingLink
{
    struct TNode *to;
    int incoming_index;
    ... link data ...
} OutgoingLink;

typedef struct TIncomingLink
{
    struct TNode *from;
    int outgoing_index;
} IncomingLink;

typedef struct TNode
{
    ... node data ...
    int num_incoming_links;
    int num_outgoing_links;
    IncomingLink *incoming_links;   // separate array
    OutgoingLink outgoing_links[1]; // embedded array starting here
} Node;

malloc(sizeof(Node) + (num_outgoing_links-1)*sizeof(OutgoingLink))ノードにスペースを割り当てるために使用します。

このアプローチでは、ノードとその発信リンクのすべてのデータが隣接するメモリ ロケーションに配置されます。

于 2012-12-24T15:09:23.170 に答える