3

これは、隣接リストのSO 投稿です。ただし、単一リンクリストとの違いはありませんか? また、これはウィキペディアの記事で、パスグラフではないグラフがある場合、リスト内のすべてのエッジ (グラフ、離散数学タイプ) であると述べています。隣接リストをコーディングするにはどうすればよいですか?

4

3 に答える 3

5

簡単な例：頂点タイプがあるとしますVertex。グラフは頂点のセットで構成されており、次のように実装できます。

std::unordered_set<Vertex> vertices;

ここで、グラフにエッジがある頂点のペアごとに、そのエッジを記録する必要があります。隣接リスト表現では、頂点のペアである可能性のあるエッジタイプを作成し、隣接リストは単にそのようなエッジのリスト（またはセット）である可能性があります。

typedef std::pair<Vertex, Vertex> Edge;
std::list<Edge> edges_as_list;
std::unordered_set<Edge> edges_as_set;

（無向グラフ(a,b) == (b,a)がある場合は、最後のセットに無向コンパレータを提供することをお勧めします。）

一方、隣接行列表現を作成する場合は、代わりにboolの配列を作成し、それらの間にエッジがある頂点を示します。

bool edges_as_matrix[vertices.size()][vertices.size()]; // `vector` is better
// edges_as_matrix[i][j] = true if there's an edge

（このためには、頂点を列挙する方法が必要になります。無向グラフでは、隣接行列は対称です。有向グラフでは、対称である必要はありません。）

エッジが少ない場合はリスト表現が適していますが、エッジが多い場合はマトリックス表現が適しています。

于 2011-10-19T02:11:08.530 に答える
3 
struct Node {
    std::vector<std::shared_ptr<Node>> Neighbors;
};
struct AdjacencyList{
    std::vector<std::shared_ptr<Node>> Nodes;
};

AdjacencyListすべての の配列を保持し、NodeそれぞれNodeがリスト内の他のすべての へのリンクを持っていますNode。技術的にはAdjacencyListクラスは必須ではなく、必要なのは astd::shared_ptr<Node> root;だけですが、 a を持つ theAdjacencyListを使用するとvector、それらを反復処理したり、他の多くのことをはるかに簡単に実行したりできます。

A----B  F
|    |\
|    | \
C    D--E

AdjacencyListA、B、C、D、E、およびへのポインタを保持しますF。
Aと へのポインタがBありCます。とへの
BポインタがAあります。へのポインタがあります。と へのポインタがあります。 と へのポインタがあります。他のノードへのポインタはありません。 DE
CA
DBEEBD
F

AdjacencyList には、Node値ではなくポインターを含める必要があります。そうしないと、サイズが変更されると、すべてのNeighborsポインターが無効になります。

于 2011-10-19T01:54:53.567 に答える
2

そのため、Boost には、boost::graph の一部として adjacency_list コンテナーが含まれています。

一般に、隣接リストは単独でリンクされたリスト以上のものです。これは、任意の頂点からグラフ内の他の頂点への (場合によっては、特定の方向の) 直接接続を表します。

ブーストのドキュメントには、いくつかの基本的な例が写真付きで提供されています。

于 2011-10-19T01:55:07.617 に答える