图

图，是一种比树更为复杂的数据结构，树的节点之间是一对多的关系，并且存在父与子的层级划分，而图的顶点（注意在此不叫节点）之间是多对多的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。

表示：G = (V, E)，其中，G 表示一个图，v 是图 G 中顶点的有穷非空集合，E 是图 G 中边的有限集合。

一、相关概念

顶点（Vertex）
- 始点（弧尾）：使用 u 表示；
- 终点（弧头）：使用 v 表示；
边（Edge）
- 无向边（边）：使用 (u, v) 表示；
- 有向边（弧，arc）：使用 <u, v> 表示；
权（Weight）：在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边上的权。权可以表示从一个顶点到另一个顶点的距离、时间或代价等含义。
网（Network）：边上标识权的图。
顶点的度（Degree）：图中与该顶点相关联边的数目。顶点 v 的度记为 D(v)。
- 入度（In Degree）：顶点 v 的入边数目，称为该顶点的入度，记为 ID(v)。
- 出度（Out Degree）：顶点 v 的出边数目，称为该顶点的出度，记为 OD(v)。
路径（Path）：从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径；
- 简单路径（Simple Path）：路径上没有重复顶点；
  - 简单开路径：起点和终点不同；
  - 简单闭路径：起点和终点相同；
- 回路（环，Circuit）：如果路径中第一个顶点和最后一个顶点相同，则此路径称为“回路”
  - 简单回路（简单环，Simple Circuit）：除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路叫简单回路。

为什么使用 u 和 v 来表示始点和终点？

It stands to reason, within all this letters, that U is used because it's alphabetically close to V. So the edge E is connected to the nodes (vertices) U and V.

查看解释链接

二、图的分类

无向图（Undirected Graph）

无向完全图（Undirected Complete Graph）

顶点集：V = {1, 2, 3, 4}
边集：E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

有向图（Directed Graph）

有向完全图（Directed Complete Graph）

顶点集：V = {1, 2, 3, 4}
弧集：E = {<1, 2>, <2, 1>, <1, 3>, <3, 1>, <1, 4>, <4, 1>, <2, 3>, <3, 2>, <2, 4>, <4, 2>, <3, 4>, <4, 3>}

有向无环图（Directed Acyclic Graph, DAG）

顶点集：V = {1, 2, 3, 4}
弧集：E = {<1, 2>, <1, 3>, <1, 4>, <3, 2>, <4, 3>}

关于 DAG 和拓扑排序，传送门

稀疏图（Sparse Graph）

有很少条边或弧（边的条数 |E| 远小于 |V|²）的图称为稀疏图（Sparse Graph）。

稠密图（Dense Graph）

边的条数 |E| 接近 |V|²，称为稠密图（Dense Graph）

稀疏图和稠密图有绝对的边界吗？

稠密图与稀疏图判断方式没有绝对的标准，可以依据定义来判断，比如边的条数 |E| 很接近 |V|²，那么毫无疑问是个稠密图。现在主要的说法是以 m = nlogn 作为区别稀疏图与稠密图的标准，实际上这个说法也不是很准确，但是考虑到实际场景中的数据，我们构造的图的边大多数时候是很显然远大于 nlogn 或者远小于 nlogn 的，所以用这个方式判断也是合理的。

三、图的表示

3.1 邻接矩阵（Adjacency Matrix）

...

3.2 邻接表（Adjacency List）

对于边数相对顶点较少的图，领接矩阵存在对存储空间的极大浪费的。可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。也就是说，对于稀疏图，使用邻接表存储会是一个更好的选择。

领接表是由两部分组成。顶点用一个一维数组存储。而每个顶点的所有邻接点构成一个线性表，由于领接点的个数不定，所以用单链表存储，无向图称为顶点 vi 的边表，有向图则称为顶点 vi 作为弧尾的出边表。

Java 中使用邻接表表示图

顶点：如果顶点是 0 ~ N 的数字，那么可以直接用数字 N 表示顶点即可。否则的话，可以使用 List<String> 来存储顶点；
邻接点：如果顶点是 0 ~ N 的数字，那么可以直接使用 List<List<Integer>> 来存储邻接点。否则的哈，可以使用 Map<String, List<String>> 来存储邻接点。

// Driver code
public static void main(String[] args)
{
    // Number of nodes
    int V = 4;

    // Edges
    List<List<Integer> > edges = new ArrayList<>();
    edges.add(Arrays.asList(0, 1));
    edges.add(Arrays.asList(1, 2));
    edges.add(Arrays.asList(3, 1));
    edges.add(Arrays.asList(3, 2));

    // Graph represented as an adjacency list
    List<List<Integer> > adjacencyList = new ArrayList<>(V);
    for (int i = 0; i < V; i++) {
        adjacencyList.add(new ArrayList<>());
    }

    for (List<Integer> i : edges) {
        adjacencyList.get(i.get(0)).add(i.get(1));
    }

    topologicalSort(adjacencyList, V);
}

3.3 十字链表（Orthogonal Linked List）

...

∞、参考链接

Glossary of graph theory 维基百科
图论相关概念 OI Wiki

Graph Theory - tenji/ks GitHub Wiki

图

一、相关概念