图的基本概念

引言

当我们提到图时，脑海中浮现的通常是用于建模数据的传统图表。但在计算机科学中，“图”这一术语有着完全不同的含义。

图数据结构在多个应用中扮演着基础性角色，例如全球定位系统（GPS）、神经网络、点对点网络、搜索引擎爬虫，甚至社交网络网站。

本节将探讨图的功能与强大之处，并了解它们如何被用来解决各种各样的问题。

现在，让我们来深入理解图的本质。

图的结构

图是由一组节点通过网络形式相互连接而成的集合。首先，我们定义图的两个基本组成部分。

顶点

顶点是图中最核心的部分。多个顶点的集合构成了一个图。从这个意义上说，顶点类似于链表中的节点。

边

边是连接两个顶点的纽带。根据图的类型，边可以是单向的或双向的。此外，边还可以带有权重（稍后会详细讨论）。

以下是图的一个可视化表示：

图的性质通常用一些术语来描述。

图的相关术语

1. 顶点的度：与某个顶点相连的边的总数。度分为两种类型：

   • 入度：指向该顶点的边的总数。
   • 出度：从该顶点出发的边的总数。

2. 平行边：对于无向图，如果两条边的两个端点相同，则称它们为平行边；对于有向图，如果两条边的起点和终点完全相同，则称为平行边。

3. 自环：当一条边的起点和终点是同一个顶点时，称为自环。

4. 邻接：如果两个顶点之间存在一条直接连接的边，则称这两个顶点是邻接的。

在上图中，顶点 a 和 b 的入度均为 1，出度也均为 1。顶点 c 因包含一个自环，其入度和出度均为 2。