[解決済み] グラフ実装 C++

質問

c++でグラフの実装を手っ取り早く書けないかと考えています。私は、グラフアルゴリズム（BFS、DFS、クラスカ、ダイクストラなど）を使用し、操作しやすいデータ構造が必要です。 私はアルゴリズムオリンピックのためにこの実装が必要なので、データ構造を書くのが簡単であればあるほどよいです。

このようなDS（主な構造体またはクラスとその中に入るもの）を提案してもらえますか？隣接リストと隣接行列が主な可能性であることは知っていますが、私はより詳細な コード のサンプルです。

例えば、前回DFSのグラフを実装することになったとき、このDSについて考えたんです。

struct Edge {
  int start;
  int end;
  struct Edge* nextEdge;
}

そして、i番目のノードから始まるエッジを表すエッジリスト(struct Edge)をi番目の場所に含むサイズnの配列を使用します。

しかし、このグラフをDFSしようとすると、10個ほどのwhileループを含む50行のコードを書かなければなりませんでした。

どんな「良い」実装があるのでしょうか？

どのように解決するのか？

どのようなアルゴリズムを実装する必要があるかに依存し、特効薬はありません（これは驚くべきことではありませんが、プログラミングの一般原則は一般原則がないということです;-)。).

有向マルチグラフをポインタを使ったノード・エッジ構造で表現することになることが多いのですが......具体的には。

struct Node
{
    ... payload ...
    Link *first_in, *last_in, *first_out, *last_out;
};

struct Link
{
    ... payload ...
    Node *from, *to;
    Link *prev_same_from, *next_same_from,
         *prev_same_to, *next_same_to;
};

つまり、各ノードは2重にリンクされた着信リンクのリストと、2重にリンクされた発信リンクのリストを持っているのである。各リンクは from と to ノードから出力されるすべてのリンクのリストです。 from ノードに到着するすべてのリンクのリストと、同じ to ノードがあります。

ポインター prev_same_from と next_same_from から出てくるすべてのリンクの連鎖をたどる場合に使用されます。 から 同じノードのポインタ prev_same_to と next_same_to を指すすべてのリンクのチェーンを管理するときに使用されます。 から は同じノードです。

ポインタをたくさん使うので、ポインタが好きな人以外は忘れてください）しかし、問い合わせと更新の操作は効率的です。例えば、ノードやリンクを追加するのはO(1)、リンクを削除するのはO(1)、ノードxを削除するのはO(deg(x))といった具合です。

もちろん、ペイロードサイズ、グラフサイズ、グラフ密度などの問題によっては、このアプローチはメモリに対して過剰な負荷となります（ペイロードに加えて、ノードあたり4ポインタ、リンクあたり6ポインタが必要です）。

似たような構造の完全な実装は以下の通りです。 こちら .