图的简单介绍

什么是图（Graph）

图（Graph） 是一种由节点（Vertex）和边(Edge)组成的数学结构，用于表示对象间的关系。图中的节点代表实体，而边则表示节点之间的关系或连接。

• 节点（Vertex） ：图中的基本单位，代表某个实体。
• 边（Edge） ：连接两个节点的线条，表示节点之间的关系或交互。

图的表示方法

图有多种表示方式，常见的有以下几种：

1. 邻接矩阵（Adjacency Matrix）

   • 使用一个二维矩阵来表示图的结构。如果图中有n个节点，那么矩阵的大小为n×n。矩阵中的元素表示节点之间是否存在边。
   • 优点：适合稠密图（节点较多且边也多的图）。
   • 缺点：空间复杂度较高，尤其在稀疏图中，会浪费大量空间。

   示例：考虑下面有4个节点的图，邻接矩阵表示方法如下：

   1 ----- 2
   |       |
   |       |
   4-------3
   

   	1	2	3	4
   1	0	1	0	1
   2	1	0	1	0
   3	0	1	0	1
   4	1	0	1	0

2. 邻接表（Adjacency List）

   • 使用一个链表（或数组）来存储每个节点的邻居节点。每个节点都有一个列表，包含所有与之相连的节点。
   • 优点：节省空间，适合稀疏图。
   • 缺点：在查找边的存在时效率较低。

   示例：上述图的邻接表表示为：

   1 → [2, 4]
   2 → [1, 3]
   3 → [2, 4]
   4 → [1, 3]