什么是邻接表，你如何编码？ [英] What is an adjacency list and how do you code one?

问题描述

以下是邻接表的 SO帖。但是我看到单链表没有什么区别？此外，这里还有一个维基百科文章，它说它是所有的边缘（图形，离散数学类型）在一个非常宽泛的列表，如果我有一个图，这不是一个路径图。

一个简单的例子：假设你有一个顶点类型顶点。它们的图形由一组顶点组成，您可以实现它们：

  std :: unordered_set&顶点; 
  

现在对于图中有边缘的每对顶点，边缘。在邻接列表表示中，您将创建一个可以是一对顶点的边缘类型，并且您的邻接列表可以是这样的边缘的列表（或者一组）：

  typedef std :: pair< Vertex，Vertex>边缘; 
 std :: list< Edge> edges_as_list; 
 std :: unordered_set< Edge> edges_as_set; 
  

（您可能需要为最后一个集合提供一个非定向比较器，

如果您有一个

无向图，则（a，b）==（b，a）邻接矩阵表示，你会创建一个bools数组，并指明哪些顶点之间有边：

  bool edges_as_matrix [vertices.size（）] [vertices.size（）]; //`vector` is better 
 // edges_as_matrix [i] [j] = true如果有边缘
  

（对于这个，你需要一个枚举顶点的方法。在无向图中，邻接矩阵是对称的;在有向图中它不需要。）

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

Here is an SO post of an adjacency list. However I see no difference from a single-linked list? Also here is a wikipedia article which says that it is all the edges (of a graph, discrete math type) in a list which is pretty broad, if I have a graph, which is not a path graph. How do I code an adjacency list?

解决方案

A simple example: Suppose you have a vertex type Vertex. They your graph consists of a set of vertices, which you can implement as:

std::unordered_set<Vertex> vertices;

Now for every pair of vertices between which there is an edge in your graph, you need to record that edge. In an adjacency list representation, you would make an edge type which could be a pair of vertices, and your adjacency list could simply be a list (or again a set) of such edges:

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

(You will probably want to supply the last set with an undirected comparator for which (a,b) == (b,a) if you have an undirected graph.)

On the other hand, if you want to make an adjacency matrix representation, you would instead create an array of bools and indicate which vertices have edges between them:

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

(For this you would need a way to enumerate the vertices. In an undirected graph, the adjacency matrix is symmetric; in a directed graph it need not be.)

The list representation is better if there are few edges, while the matrix representation is better if there are a lot of edges.

这篇关于什么是邻接表，你如何编码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！