什么是邻接列表,你如何编码？

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数组,并指出哪些顶点之间有边:

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

(为此你需要一种枚举顶点的方法.在无向图中,邻接矩阵是对称的;在有向图中它不一定是.)

如果边缘很少,则列表表示更好,而如果存在大量边缘,则矩阵表示更好.