🏷️ 知识点：边数统计

对 n 个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问：

1. 如何判别图中有多少条边？
2. 如何判别任意两个顶点 i 和 j 是否有边相连？
3. 任意一个顶点的度是多少？

[tag_link]

参考答案

1. 边数

• 邻接矩阵：无向图的非零（无权图即为 1）元素数为 2e，边数为非零元素数除以 2；有向图的非零元素数就是弧数 e。
• 邻接表：无向图每条边有两个边表结点，边数为边表结点总数除以 2；有向图的边表结点总数就是弧数。

2. 判断相邻

邻接矩阵中，无向图检查 A[i][j]（等价地检查 A[j][i]），有向图检查 A[i][j] 是否表示弧 i→j。邻接表中，扫描顶点 i 的边链表查找 j；无向图还可从 j 的链表查找 i。

3. 顶点度

邻接矩阵中，无向图顶点 i 的度是第 i 行（或列）的非零元素数；有向图第 i 行非零元素数为出度，第 i 列非零元素数为入度，度为二者之和。邻接表中，无向图顶点 i 的度是其边链表长度；有向图该链表长度为出度，入度需统计所有边表中指向 i 的结点，度为入度与出度之和。

易错点

无向图邻接表的边存储两次，而有向图每条弧只存储一次；有向图邻接表的链表长度只是出度，不能直接当作总度。