图的基础知识：从邻接矩阵到邻接表

### 1. 介绍：图的基本概念和定义

图是一种抽象的数学结构，由节点（顶点）和连接节点的边组成。图可以用来模拟各种实际问题，如社交网络中的用户关系、交通网络中的道路连接等。图论作为离散数学的一个分支，在计算机科学、数据结构、人工智能和网络等领域有着广泛的应用。

#### 1.1 什么是图

图可以用G(V, E)来表示，其中V表示节点的集合，E表示边的集合。边可以是有向的，也可以是无向的，图分为有向图和无向图。有向图中的边是有方向的，无向图中的边是没有方向的。

#### 1.2 图的应用领域

图在计算机科学领域有着广泛的应用，比如在算法设计中，常常需要用图来表示问题实例。社交网络分析、路由算法、拓扑排序、最短路径算法等都与图相关。

#### 1.3 图的基本属性和概念

- 路径：图中连接顶点的边的序列称为路径，路径的长度是路径上的边的数量。
- 连通性：图中任意两个顶点之间都有路径存在，则称为连通图，否则为非连通图。
- 度：顶点的度是指与顶点相关联的边的数目。
- 环：如果图中一条路径的起点和终点是同一个顶点，且路径中除起点和终点外其它顶点各不相同，则这样的路径称为环。

### 2. 邻接矩阵：图的一种表示方法

#### 2.1 邻接矩阵的定义和特点

邻接矩阵是一种常见的图的表示方法，它使用二维数组来表示图的连接关系。对于有n个顶点的图，邻接矩阵是一个n*n的矩阵，如果顶点i和顶点j之间有边相连，则对应的矩阵元素a[i][j]为1，否则为0（针对无向图）。对于有向图，如果有一条从顶点i到j的边，则a[i][j]为1，否则为0。

#### 2.2 邻接矩阵的优点和缺点

优点:
- 方便查找任意两个顶点之间是否有边相连。
- 方便计算顶点的度。

缺点:
- 对于稀疏图（边相对较少）来说，邻接矩阵占用大量的空间。
- 插入和删除边的操作复杂度较高。

#### 2.3 邻接矩阵的应用场景

- 适用于稠密图（边相对较多）。
### 3. 邻接表：另一种图的表示方法

邻接表是一种常见的图的表示方法，它使用链表来表示图中的顶点和边，相比于邻接矩阵，邻接表在存储稀疏图时有一定的优势。

#### 3.1 邻接表的定义和结构

在邻接表中，图中的每个顶点都对应一个链表，链表中存储了与该顶点相邻的其他顶点。如果图中有n个顶点，那么邻接表就由n个链表组成，每个链表记录了与对应顶点相连的其他顶点信息。

#### 3.2 邻接表的存储方式

邻接表可以使用数组和链表结合的方式进行存储，通常使用数组来存储所有顶点的信息，数组中的每个元素指向一个链表，这个链表记录了与对应顶点相连的其他顶点。

#### 3.3 邻接表的优点和缺点

邻接表的优点在于对存储空间的利用率高，特别适合表示稀疏图；同时在查找某个顶