画出下图的邻接矩阵和邻接表

邻接矩阵和邻接表是图论中常见的两种表示无向图或有向图的数据结构，它们分别以矩阵和链表的形式记录图中各个节点之间的连接关系。本文将以一张简单的图为例，介绍如何绘制该图的邻接矩阵和邻接表，并对它们的特点、使用场景及优缺点等方面进行分析。

首先，我们先来看下面这张图：


它由 6 个节点和 7 条边构成，每条边都表示两个节点之间的连接关系。接下来我们分别绘制它的邻接矩阵和邻接表。

邻接矩阵

邻接矩阵通常用二维数组来表示，其中数组下标对应节点编号，数组元素表示两个节点间是否有连线。具体地，邻接矩阵中存储的是图的连接关系，$A[i][j]=1$ 表示第 i 个节点和第 j 个节点之间存在连线，$A[i][j]=0$ 则表示两个节点之间没有连线。

对于上图，我们可以画出其邻接矩阵如下：

$$

\left[ \begin{matrix}

0 & 1 & 0 & 0 & 1 & 1 \\

1 & 0 & 1 & 0 & 0 & 0 \\

0 & 1 & 0 & 1 & 0 & 0 \\

0 & 0 & 1 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 1 \\

1 & 0 & 0 & 0 & 1 & 0 \\

\end{matrix}\right]

$$

图中共有 6 个节点，对应邻接矩阵的 6 行 6 列。每一行（或列）表示该行（或列）对应节点的连接关系，取值为 0 或 1。如第 1 行表示节点 1 对应的连接情况，其中 $A[1][2]=1$，表示节点 1 和节点 2 之间存在连线。

邻接表

邻接表则是用链表来表示图的数据结构，将图中每个节点所连接的节点以链表的形式存储。具体地，邻接表中保存了与每个节点相邻接的节点的列表，即一个链表或数组，每个元素表示从该节点出发可以直接到达的节点。

对于上图，我们可以绘制出其邻接表如下：

```

1 -> 2 -> 5 -> 6

2 -> 1 -> 3

3 -> 2 -> 4

4 -> 3

5 -> 1 -> 6

6 -> 1 -> 5

```

邻接表中一共有 6 个链表，每个链表对应图中的一个节点。如第一个链表即表示与节点 1 相邻接的其他节点，由于1 与 2、5、6 相邻接，所以链表中元素依次为 2、5、6。

邻接矩阵和邻接表的比较

邻接矩阵和邻接表在表示图的时候，各有各的优缺点。下面我们对它们进行比较。

1. 存储方式：邻接矩阵中使用二维数组存储图的关系，因此需要预先分配 $n^2$ 的空间，对于稀疏图来说这样会造成一些空间浪费。而邻接表则使用链表或数组来表示节点之间的关系，在存储稀疏图时会更加节省空间。

2. 访问效率：对于邻接矩阵，给定两个节点，如果我们要判断它们之间是否有连线，只需要直接读取对应的数组元素，访问效率为 $O(1)$；而对于邻接表，由于需要遍历链表中的元素来寻找相邻的节点，所以平均访问效率为 $O(k)$，其中 $k$ 表示该链表的长度。因此在大多数情况下，邻接矩阵的访问效率更高。

3. 构建时间：邻接矩阵的构建时间为 $O(n^2)$，其中 $n$ 表示节点数。而邻接表的构建时间取决于图的边数，因为每一条边都需要添加到对应的链表中。因此，在图的边比较少的情况下，邻接矩阵的构建效率更高；而在图的边比较多时则更适合用邻接表来表示。

邻接矩阵和邻接表的使用场景

邻接矩阵和邻接表的使用场景各有不同，视情况而定。一般来说，邻接矩阵适用于节点较少，但节点之间边比较多的图；而邻接表则适用于节点较多，但节点之间边比较少的图。此外，在需要对节点之间的连通性进行深入分析时，使用邻接矩阵的效率更高。