举例说明邻接矩阵

假设有一个无向图，其中有4个顶点，它们分别用字母A、B、C、D表示，图中的边如下所示：

A -- B
|    |
C -- D

可以用邻接矩阵表示这个图，如下所示：

   A  B  C  D
A  0  1  1  0
B  1  0  0  1
C  1  0  0  1
D  0  1  1  0

矩阵中的第一行和第一列分别代表顶点A，第二行和第二列分别代表顶点B，以此类推。矩阵中的元素表示两个顶点之间是否有边相连，如第一行第二列的元素1表示顶点A和顶点B之间有一条边相连，而第二行第三列的元素0则表示顶点B和顶点C之间没有边相连。

相关问题

有向图的邻接矩阵举例说明

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，邻接矩阵就是n*n的二维矩阵，可以用矩阵中的值的不同来表示不同顶点之间的关系。对于有向图而言，邻接矩阵中的元素a[i][j]表示从顶点i到顶点j是否有一条有向边，如果有，则a[i][j]=1，否则a[i][j]=0。下面是一个有向图的邻接矩阵举例：

假设有一个有向图G，它有5个顶点，分别为V={V1,V2,V3,V4,V5}，边集为E={E1,E2,E3,E4,E5,E6,E7,E8}，其中E1=(V1,V2)，E2=(V1,V3)，E3=(V2,V3)，E4=(V2,V4)，E5=(V3,V4)，E6=(V4,V1)，E7=(V4,V5)，E8=(V5,V3)。那么这个有向图的邻接矩阵为：

0 1 1 0 0
0 0 1 1 0
0 0 0 1 0
1 0 0 0 1
0 0 1 0 0

其中，第i行第j列的元素为1表示从顶点i到顶点j有一条有向边，为0表示没有有向边。例如，第1行第2列的元素为1，表示从顶点V1到顶点V2有一条有向边。

有向图无环图的邻接矩阵按上三角，行优先压缩存储，请举例说明怎么进行压缩存储

有向图无环图（DAG）的邻接矩阵按上三角，行优先压缩存储是一种用于节省存储空间的技巧，特别是在处理稀疏的有向图时非常有效。这种方法的核心思想是只存储有向图的上三角部分（包括对角线）的邻接信息，因为无环图的邻接矩阵是对称的，上三角的信息足以重建整个图。

具体步骤如下：
1. 创建一个一维数组 `adj` 用于存储压缩后的数据。
2. 初始化一个变量 `pos` 用于记录 `adj` 数组当前的存储位置。
3. 从上三角开始遍历邻接矩阵的每一个元素（不包括对角线上的元素），按行优先的顺序将非零元素（即存在边的元素）按顺序存储到 `adj` 数组中，并更新 `pos`。
4. 存储时，可以只记录目标顶点的索引，也可以记录边的权重（如果有权重的话）。
5. 最终，`adj` 数组和 `pos` 变量就足以表示这个有向图的上三角部分。

下面以一个具体的例子进行说明：

假设有一个有向图无环图的邻接矩阵如下：

0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0

这个矩阵表示有5个顶点，顶点间的有向边如下：
- 顶点1指向顶点2
- 顶点2指向顶点3
- 顶点3指向顶点4
- 顶点4指向顶点5

按照上三角，行优先的顺序，我们从顶点2开始（因为顶点1是第一个，它没有前驱），遍历矩阵的上三角部分，结果如下：

1 -> 2
2 -> 3
3 -> 4
4 -> 5

假设我们使用一个一维数组 `adj` 来存储这些边的信息，可以得到如下：

adj[0] = 2  // 顶点1指向顶点2
adj[1] = 3  // 顶点2指向顶点3
adj[2] = 4  // 顶点3指向顶点4
adj[3] = 5  // 顶点4指向顶点5

数组中的每个元素代表了原邻接矩阵中对应上三角的非零元素的列索引，数组的长度即为 `pos` 的值。