图是网络结构的抽象模型，由一组 边 和 顶点 组成。下图就是一个典型的图结构：

相关术语

1. 顶点：图里面一个一个数据元素被称之为 顶点。之前在线性表中称之为元素，树里面称之为节点。

   另外，线性表可以没有元素（空表），树里面可以没有节点（空树），但是在图结构中不能够没有顶点。

2. 相邻顶点：由一条边连接在一起的两个顶点，称之为相邻顶点。

3. 度：一个顶点的相邻顶点的数量。

4. 路径：指的是一连串顶点序列。其中有一个概念称之为 简单路径，指的就是 不包含 重复顶点的路径。

5. 环：从某一个顶点出发，最后回到该顶点，形成了一个闭环。环也会算作是一个简单路径。

无向图和有向图

1. 无向图：顾名思义就是 顶点之间是没有方向的

由于是无方向的，因此连接 A 和 D 的边，可以表示为 (A, D)，也可以写成(D, A)。对于无向图来讲，G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {(A,B), (B,C), (C,D), (D,A), (A,C)}

在无向图中，如果每一个顶点都和其他所有顶点相连，则称该无向图为 无向完全图。如下图所示：

一个含有 n 个顶点的无向完全图拥有

$$\frac{n*(n-1)}{2}$$

条边。例如上面的无向完全图有 4 个顶点，根据公式计算出拥有 6 条边。

2. 有向图：顶点之间 有明确的方向

有向图是有方向的，使用 尖括号 来表示，尖括号中的第一个节点表示 tail，第二个节点表示 head。例如上图为 G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {<A,D>, <B,A>, <C,A>, <B,C>}。

在有向图中，如果 任意两个顶点之间都存在方向相反的指向，称之为 有向完全图。例如下图就是一个有向完全图：

加权图

图还可以是加权的。如下图所示，加权图的 边被赋予了权值。

子图

假设有两个图，一个图是 G = (V, {E})，另一个图是 G' = (V', {E'})，如果

$$\begin{aligned} V' &\subseteq V \\ E' &\subseteq E \end{aligned}$$

那么我们称 G’ 为 G 的子图。

举个例子：

---

-EOF-