数据结构之图

图是一种非线性结构，是一组有限个顶点(vertices)和一组连接顶点的边(edges)的集合。

一般来说，图 G 记作 G=(V, E)，V 是图中顶点集合，E 是图中边的集合。

例子：G = (V, E), V = {A, B, C, D, E}, E = {(A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)}
  A ──── B
  | \    | \
  |   \  |   E
  |     \| /
  C ──── D

图的术语

顶点

图的单个数据元素叫顶点(Vertex)，也叫节点(node)。

边

一条边连接两个顶点，边也叫弧(Arc)。

无向图

若图中的每条边都是无方向的，顶点 V_i和顶点 V_j之间的边用(V_i, V_j)表示。

因此，在无向图中(V_i, V_j)与(V_j, V_i)表示同一条边。无向图是用小括号。

有向图

若图中的每条边都是有方向的，顶点 V_i和顶点 V_j之间的关系用<V_i, V_j>表示。

它表示的是从 V_i到 V_j有一条有向边，V_i是这条有向边的起点，V_j是这条有向边的终点。

因此，在有向图中<V_i, V_j>与<V_j, V_i>分别表示两条边。有向图是用尖括号。

完全图

无向完全图。即一个无向图具有 n 个顶点，而每一个顶点与其他 n-1 个顶点之间都有边，则称之为无向完全图。含有 n 个顶点的无向完全图共有 n _ (n - 1) / 2 条边。

有向完全图。即一个有向图具有 n 个顶点，任意两个不同的顶点之间都有方向相反的两条弧存在，称之为有向完全图。含有 n 个顶点的有向方向图有 n _ (n - 1)条边。

度

顶点 V 的度是指该顶点上边的数目，记作 D(v)。若 G 为有向图，顶点的度为该顶点的入度和出度之和。顶点的入度是以该顶点为终点的有向边的数目。而顶点的出度以该顶点为起点的有向边的数目，分别记作 ID(v)和 OD(v)。

路径

在无向图 G 中，从顶点 V_p到顶点 V_q的路径是指存在一个顶点序列 V_p, V_i1, …, V_in, V_q, 使得(V_p, V_i1), …, (V_in, V_q)均属于 E(G)。若是有向图 G，则 E(G)中的有向边<V_p, V_i1>, …, <V_in, V_q>组成。

路径的长度，就是该路径经过的边的数目。

路径的回路，就是该路径的起始点和终点都指向同一个节点。

简单路径，就是该路径上除了起始点和终点可以相同外（不一定非要相同，可以相同），其余顶点均不相同。

连通图和连通分量

在无向图 G 中，若任意两个顶点 V_i到顶点 V_j有路径，则称顶点 V_i和顶点 V_j是连通的。如果无向图 G 中任意两个顶点都是连通的，则称其为连通图。

无向图 G 的极大连通子图称为 G 的连通分量。

强连通图和强连通分量

连通图和连通分量是针对无向图，而强连通图和强连通分量是针对有向图。

在有向图 G 中，若任意两个顶点 V_i到顶点 V_j，从顶点 V_i到顶点 V_j和从 V_j到顶点 V_i都存在路径，则称图 G 为强连通图。

有向图中的极大连通子图称为有向图 G 的强连通分量。

网

边带有权值的图。

图的存储结构

邻接矩阵

图的邻接矩阵表示利用一个矩阵来表示图中顶点之间的关系。对于 n 个顶点的图 G = (V, E), 其邻接矩阵是一个 n 阶方阵，且满足

          / 0  若(V₁, V₂)或<V₁, V₂>不是E中的边
A[i][j] =
          \ 1  若(V₁, V₂)或<V₁, V₂>是E中的边

图（赋权图）的邻接矩阵可定义为：

          / W  若(V₁, V₂)或<V₁, V₂>不是E中的边，W为边上的权值
A[i][j] =
          \ ∞  若(V₁, V₂)或<V₁, V₂>是E中的边

邻接链表图的邻接链表就是图的链式存储结构。在这种存储结构，图中的每个顶点都包含其相邻顶点的列表。邻接链表中的节点有表节点和表头节点两种类型。
```
           表节点                              表头节点
   ▁ ▁ ▁ ▁ ▁ ▁ ▁ ▁ ▁               ▁ ▁ ▁ ▁ ▁ ▁
  | adjvex | nextarc | info |              | data | firstarc |
   ▔ ▔ ▔ ▔ ▔ ▔ ▔ ▔ ▔               ▔ ▔ ▔ ▔ ▔ ▔
```
- adjvex: 指示与顶点 V 邻接的顶点的序号
- nextarc: 指示下一条边的节点
- info: 存储与边有关的信息，如权值等
- data: 存储顶点 V 的名或其他信息
- firstarc: 指示链表中的第一个节点（邻接顶点）

图的遍历

深度优先搜索遍历(Depth First Search, DFS)
广度优先搜索遍历(Breadth First Search, BFS)

生成树和最小生成树

生成树：一个连通图的生成树是一个极小的连通子图，它包含图中的全部顶点，但只有构成一棵树的 n-1 条边。即生成树将图中所有顶点用最少的边连通的子图。其中，按深度优先搜索遍历得到的生成树叫深度优先生成树，按广度优先搜索遍历得到的生成树叫广度优先生成树。

    A                A                A                A                A
   / \              / \              / \              /                / \
  B - C            B   C            B   C            B - C            B   C
     / \                \              / \              /                / \
    E - D            E - D            E - D            E - D            E   D
  （图）      （其中一种生成树）  （非生成树）    （DFS生成树）    （BFS生成树）

最小生成树：对于带有权值的连通图，生成树的各边也带有权值，因此把生成树各边的权值总和称为生成树的权，把权值最小的生成树称为最小生成树。

普里姆(Prim)算法普里姆算法就是以一个顶点集合作为始态，不断寻找与顶点相邻且代价最小的边的另一个顶点。
克鲁斯卡尔(Kruskal)算法