什么是图？

简介

当我们提到“图”时，通常会想到用于数据可视化的传统图表。但在计算机科学中，“图”具有完全不同的含义——它是一种用来存储和处理数据的数据结构。

图数据结构在许多应用中起着关键作用，例如 GPS 导航、神经网络、对等网络（P2P）、搜索引擎爬虫、垃圾回收机制（如 Python 中的 GC），以及社交网络网站等。

本节将深入探讨图的功能与强大之处，并了解如何利用图来解决各种实际问题。

现在，让我们来看看图究竟是什么。

图的结构

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

顶点（Vertex）

顶点是图中最基本的元素。多个顶点的集合构成一个图。从这个角度看，顶点类似于链表中的节点。

边（Edge）

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

以下是图的一个直观示意图：

为了描述图的各种性质，我们需要掌握一些常用术语。

图的相关术语

1. 顶点的度（Degree of a Vertex）：指与该顶点相关联的边的总数。分为两种类型：

   • 入度（In-Degree）：指向该顶点的入边数量。

   • 出度（Out-Degree）：从该顶点出发的出边数量。

2. 平行边（Parallel Edges）：对于无向边，若两条边的端点相同，则称为平行边；对于有向边，若两条边具有相同的起点和终点，也称为平行边。

3. 自环（Self Loop）：当一条边的起点和终点为同一顶点时，称为自环。

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

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