邻接矩阵：定义、用途及示例

邻接矩阵是一种用于表示无向图或有向图的数据结构。它以矩阵的形式表示图中各个节点之间的连通关系。矩阵中的每一个元素表示两个节点之间是否存在一条边，如果存在则为1，否则为0。对于无向图而言，邻接矩阵是对称的。

邻接矩阵可以用来进行图的遍历、最短路径、连通性等操作。

示例:

假设有一个无向图，其节点为 A、B、C、D，边为 (A, B)、(A, C)、(B, C)、(B, D)、(C, D)。

则该图的邻接矩阵为：

| | A | B | C | D | |-------|---|---|---|---| | A | 0 | 1 | 1 | 0 | | B | 1 | 0 | 1 | 1 | | C | 1 | 1 | 0 | 1 | | D | 0 | 1 | 1 | 0 |

用途:

• 图的遍历：可以通过邻接矩阵来快速判断节点之间是否相连，从而实现图的遍历。
• 最短路径：可以通过邻接矩阵来计算节点之间的最短路径。
• 连通性：可以通过邻接矩阵来判断图是否连通，以及图的连通分量。

优点:

• 简单易懂
• 容易实现
• 可以用于表示有向图和无向图

缺点:

• 对于稀疏图，邻接矩阵会浪费大量的存储空间。
• 对于大型图，邻接矩阵的存储和计算都会非常耗时。