图的基本概念与结构

引言

提到图（graph），人们通常会联想到用于表示数据的传统图表。但在计算机科学中，“图”具有完全不同的含义。

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

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

那么，什么是图呢？

图的结构

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

顶点

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

边

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

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

图的性质可以用多种术语来描述。

图的相关术语

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

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

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

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

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

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