5

私は、C ++でかなり大きく、まばらで、無向のグラフ構造を表現することを計画しています。これは10,000以上の頂点のオーダーであり、各頂点の次数は約10です。

グラフを隣接行列またはリストとして表現するための背景をいくつか読んだことがありますが、そのうちの8つは私がやりたいことに適しているようです。私のシナリオでは：

  • グラフの各エッジには、いくつかのプロパティ（数値）が付加されます
  • 最初のグラフ作成後、エッジは削除できますが、作成されることはありません
  • 頂点が作成または削除されることはありません
  • グラフの主なクエリ操作は、エッジEを検索し、他のどのエッジがそれに接続されているかを調べます。これは、Eの両端の頂点に接続されているエッジを見つけることと同じです。

隣接行列が不適切に見えるのは、この最後のポイントです。私が見る限り、各クエリには2 * Nの操作が必要です。ここで、Nはグラフ内のノードの数です。

隣接リストは必要な操作を減らすと思いますが、各エッジに含まれているパラメーターのため、つまり隣接リストがそれぞれを格納しているため、不適切と思われます。

これらのクエリ操作がより速くなり、各エッジをそのパラメーターとともに保存できるように、データを保存するためのより良い方法はありますか？私はそれを行うための正しい方法ではない何かを実装し始めたくありません。

4

2 に答える 2

7

ここでは、通常のオブジェクト指向アプローチに問題はありません。Edge<V,E>とVertex<V,E>タイプを設定します。ここVで、は頂点によって保存されたコンテンツでEあり、はエッジによって保存されたコンテンツです。各エッジには、それぞれの頂点への2つの参照と、それぞれの頂点のどのスロットでこのエッジを探すかを示す2つのインデックスがあります。

template <typename V, typename E>
class Edge {
  struct Incidence {
    size_t index;
    Vertex<V,E>& v;
  };
  std::array<Incidence,2> vertices;
  E content;
};

template <typename V, typename E>
class Vertex {
  std::vector<Edge<V,E>*> edges;
};

エッジを削除すると、の位置がの前の位置に移動しeます。一定時間の除去。特定のエッジに隣接するすべてのエッジを列挙するための線形時間（操作の結果のサイズ）。私にはいいですね。Vertex<V,E>::edgesbacke

于 2012-09-06T17:34:30.457 に答える
1

このようなものはもっともらしいと思われますか？これはエッジ隣接を保存します：

#include <vector>
#include <map>

typedef int vertex;

struct edge
{
    vertex a,b;
    // other data
};

bool operator< (const edge &a, const edge &b)
{
    unsigned long long ahash = a.a;
    ahash << 32;
    ahash |= a.b;
    unsigned long long bhash = b.a;
    bhash << 32;
    bhash |= b.b;
    return ahash < bhash;
}

// support for your query operation
typedef std::map<edge, std::vector<edge &> > edge_adjacency;

エッジを頂点にマッピングしてから、かなり標準的なものを使用したいようです。

于 2012-09-06T17:23:02.077 に答える