图的表示法——邻接表#

一、引言#

上一篇我们利用邻接矩阵实现的图具有很高效的搜索能力，所以时间复杂度很小，但是空间复杂度却很大。

也就是所谓的空间换时间嘛，并不是一个很好的解决方案。

对于每一行来说，就是一个一维数组，代表着一个节点与其他节点的关系。

我们拿A来举例子。

它的一维数组就是下图。

上方的数字代表着边的终止位置，比如1就是B。

对于这个一维数组，起始位置都是一样的，是A。

简单点说，行代表起始点，列代表终止点。

我们可以看到我们既存储了有关联的节点信息，又存储了，没有连接的节点信息。这些没有连接的信息可以说是冗余的！

二、邻接表#

实际上我们可以用{1,2,3}or{B,C,D}来表示上面的一维数组。

当然，利用索引可比name名称消耗的内存少，所以推荐使用索引。

在机器中利用数组来存储就能实现上面的效果。

如果不使用邻接矩阵，我们就可以这样做。

在cpp里面我们如何实现创建上面这种效果呢？

我们可以创建一个指针数组，里面存放指针也就是目标地址。

1
int *A[8];
2
A[0] =new int[3];
3
A[1] =new int[3];
4
A[2] =new int[2];
5
等等

使用这种方法的空间复杂度将正比于边的数量，也就是O（|E|)

现在，像是这种无向图，我们将会消耗2*边数的内存空间

而有向图就消耗边数个内存空间。

在这种情况下，判断两个是否相连接只需要扫描一行即可。时间复杂度是O（v）。

或者找到和他相连的节点，时间复杂度也是O(v)。

这看上去并没有减少咱们的时间复杂度。

但是空间复杂度确实极大减少了。

三、延申#

如果我们要实现别的操作，如下（ps：作图忘记把权重改回1了喵）

新建一处绿色的连接，在这两种结构中存储。

如果插入一个新的连接，我们在邻接矩阵里只要将对应的0取反成1即可。

在第二个结构里，我们可以在第0行的末尾加一个6.

但是我们知道，数组要实现动态需要拷贝与删除，这样又会浪费时间。

所以我们可以选择链表，它对于动态数据的处理有着天然的优势。

1
struct Node{
2
  int data;
3
  struct Node* next;
4
}
5
Node *A[8];

现在我们的邻接表就会变成这个样子，我依然没有画全哦！

像是这里的A[0]是一个节点指针，存放与A相连的第一个顶点的地址。

这样的结构，我们就把他称作为邻接表。空间复杂度可以用O(E+V)来表示。

我们还可以在结构体里定义权重，用来存放。