1) 概念

图是由顶点（vertex）和边（edge）组成的数据结构，例如

该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的

有向 vs 无向

如果是无向图，那么边是双向的，下面是一个无向图的例子

度

度是指与该顶点相邻的边的数量

例如上图中

• A、B、C、E、F 这几个顶点度数为 2
• D 顶点度数为 4

有向图中，细分为入度和出度，参见下图

• A (2 out / 0 in)
• B、C、E (1 out / 1 in)
• D (2 out / 2 in)
• F (0 out / 2 in)

权

边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。

路径

路径被定义为从一个顶点到另一个顶点的一系列连续边，例如上图中【北京】到【上海】有多条路径

• 北京 - 上海
• 北京 - 武汉 - 上海

路径长度

• 不考虑权重，长度就是边的数量
• 考虑权重，一般就是权重累加

环

在有向图中，从一个顶点开始，可以通过若干条有向边返回到该顶点，那么就形成了一个环