简介

🔍 如何定义图？

图是由一组通过边以网络形式相互连接的顶点（节点）组成的结构。

[一个包含6个节点和7条边的图]

顶点：

图中用于存储数据的基本单元，通常以节点（如1、3、7…）的形式表示，也称为顶点。

[一个包含4个顶点的图]

边：

一个二元组(x,y)被称为一条边，表示顶点x与顶点y之间存在连接。边可能带有权重或成本，用来表示从顶点x到顶点y所需的开销。

边通常用直线表示。

[一个包含3条边的图]

图的类型

常见的图有两种类型：

1. 无向图
2. 有向图

1. 无向图

在无向图中，边默认是双向的；例如，对于二元组(0,1)，表示顶点0与顶点1之间存在一条边，且没有特定方向。你可以从顶点0到达顶点1，也可以反向通行。

[一个包含3个顶点和2条边的无向图]

2. 有向图

在有向图中，边是单向的；例如，对于二元组(0,1)，表示存在一条从顶点0指向顶点1的边，只能从0走向1，不能反向通行。

[一个包含3个顶点和2条边的有向图]

图的相关术语

1. 顶点的度：与某一顶点相连的边的总数。

参考下图：

=> 顶点5的度 = 3
=> 顶点1的度 = 2
=> 顶点6的度 = 1

[一个包含6个节点和7条边的图]

顶点的度分为两种：

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

2. 平行边：连接相同两个顶点的两条或多条边。

[具有平行边的图]

3. 自环：边的两个端点为同一顶点，例如二元组(x,x)。

[一个展示自环的图]