c++ - 什么是邻接表，您如何编写邻接表？

Question

这是邻接列表的SO 帖子。但是我看不出与单链表有什么区别？这里还有一篇维基百科文章说，如果我有一个不是路径图的图，那么它是一个非常广泛的列表中的所有边（图，离散数学类型）。如何编码邻接列表？

Answer 1

一个简单的例子：假设你有一个顶点类型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 edges_as_matrix[vertices.size()][vertices.size()]; // `vector` is better
// edges_as_matrix[i][j] = true if there's an edge

（为此，您需要一种枚举顶点的方法。在无向图中，邻接矩阵是对称的；在有向图中则不需要。）

如果边缘较少，则列表表示更好，而如果边缘很多，则矩阵表示更好。

Answer 2

struct Node {
    std::vector<std::shared_ptr<Node>> Neighbors;
};
struct AdjacencyList{
    std::vector<std::shared_ptr<Node>> Nodes;
};

AdjacencyList包含所有 s 的数组Node，并且每个都Node具有指向列表中所有其他Nodes 的链接。从技术上讲，AdjacencyList该类不是必需的，只需要 a std::shared_ptr<Node> root;，但是AdjacencyList使用 a 和 avector可以使迭代它们以及许多其他事情变得容易得多。

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

AdjacencyList保存指向A, B, C, D, E, 和F的指针
A有指向B和的指针C。
B有指向AandD和的指针E。
C有指向A.
D有指向B和的指针E。 E有指向B和的指针D。
F没有指向其他节点的指针。

AdjacencyList 必须包含指针而不是Node值，否则当它调整大小时，所有Neighbors指针都会失效。

Answer 3

因此，Boost 包含一个 adjacency_list 容器作为 boost::graph 的一部分。

一般来说，邻接表不仅仅是一个单链表。它描述了图中任何顶点到其他顶点的直接连接（可能是给定方向的）。

boost 文档提供了一些带有图片的基本示例。