图的基本概念

引言

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

图数据结构在多个应用中发挥着基础性作用，例如全球定位系统（GPS）、神经网络、点对点网络、搜索引擎爬虫、垃圾回收机制，甚至社交网络网站。

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

现在，让我们来讨论一下图的本质到底是什么。

图的结构

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

顶点

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

边

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

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

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

图的相关术语

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

   • 入度：指向某个顶点的边的数量。
   • 出度：从某个顶点出发的边的数量。

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

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

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

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