什么是邻接表?如何编写邻接表？

Question

这是邻接列表的SO post。然而，我看不出与单链表有什么不同？这里还有一个wikipedia article，它说它是一个列表中的所有边(图，离散数学类型)，如果我有一个图，这不是一个路径图，那么这个列表是相当广泛的。如何对邻接表进行编码？

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包含所有Node的数组，并且每个Node都有指向列表中所有其他Node的链接。从技术上讲，AdjacencyList类并不是必需的，所需要的只是一个std::shared_ptr<Node> root;，但是拥有一个带有vector的AdjacencyList使得遍历它们和其他许多事情变得容易得多。

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

AdjacencyList包含指向A、B、C、D、E和F的指针。

A有指向B和C的指针。

B有指向A、D和E的指针。

C有指向A的指针。

D有指向B和E的指针。E有指向B和D的指针。

F没有指向其他节点的指针。

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

Answer 3

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

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

boost docs提供了几个基本示例，并附有图片。