图的定义

图(Graph) 由 顶点(Vertex) 和 边(Edge) 组成，每条边的两端都必须是两个顶点。

二元组定义

图 G 是一个 有序二元组 (V, E)，其中 V 称为 顶集 (Vertices Set)，E 成为 边集 (Edges Set)，E 与 V 不相交。

E 的元素都是二元组，用 (x, y) 表示，其中 x, y ∈ V

术语

阶 (Order)：图 G 中顶集 V 的大小。
子图 (Sub-Graph)：当图 G’ = (V’, E’) 其中 V‘ 包含于 V，E’ 包含于 E，则 G’ 称作图 G = (V, E) 的子图。
- 每个图都是本身的子图。
生成子图 (Spanning Sub-Graph)：指满足条件 V(G’) = V(G) 的 G 的子图 G’。
度（Degree）：与该顶点相连的边和条数。
- 入度 (In-degree) 和 出度 (Out-degree)：对有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
自环 (loop)：若一条边的两个顶点为同一顶点，则此边称作自环。
路径 (Path)：从 u 到 v 的一条路径是指一个序列： v0，e1，v1，e2，v，……ek，vk，其中 ei 的顶点为 vi 及 vi - 1
- k 称作路径的长度
- 如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。
- 简单路径 (Simple Path)：起始顶点与终止顶点重合以外，所有顶点两两不相等
桥 (Bridge)：去掉该条边，便会使得整个图不连通
连通分量：无向图的极大连通子图
强连通分量：有向图的极大强连通子图

图的存储

图的存储方式有两种：邻接矩阵、邻接表

邻接矩阵

邻接矩阵为一个二维数组 G[N][N] ，0 ~ N - 1 对应图的顶点， G[i][j] == 1 表示顶点 i、j 之间有边，G[i][j] == 0 表示没有边

G[i][j] 也可以表示边的权值，不存在的边可以设为 0、-1 或一个很大的数

特点：实现简单，但是占用内存较大

邻接表

0 ~ N - 1 对应图的顶点，把一个顶点的所有出边看作一个集合/列表，则 N 个顶点有 N 个集合，这 N 个集合称为图的 邻接表，记为 Adj[N]。

通常邻接表是通过链表数组实现的，但是我们可以较为简单地使用 vector 来实现邻接表
1
vector<int> adj[N];
如果是有权图，这 vector 存储的是一个结构体

特点：比邻接矩阵节省空间

图的遍历

图的遍历方式有两种：DFS、BFS

DFS

以深度作为第一关键词，每次都是沿着路径到不能再前进时才退回到最近的岔路口。

dfs(u) {
	vis[u] = true;
    for (u 的邻居 v && vis[v] == false)
        dfs(v);
}

dfsTravese(G) {
    for (G 所有的顶点 u)
        if (vis[u] == false)
            dfs(u);
}

BFS

以广度作为第一关键词，每次以扩散的方式向外访问顶点。

bfs(G) {
	queue q;
    inq[u] = true;
    while (q 非空) {
        取出 q 的队首 u;
        for (u 的邻居 v && inq[v] == false)
            v 入 q;
            inq[v] = true;
    }
}

bfsTravese(G) {
    for (G 所有的顶点 u)
        if (inq[u] == false)
            bfs(u);
}

应用

判断一个图是否有环
找出一个图之间的最短路径