无向图

1. 回路或环：第一个顶点和最后一个顶点相同的路径。
2. 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
3. 连通：顶点 v 至 v’ 之间有路径存在
4. 连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。
5. 连通分量：极大连通子图，子图中包含的顶点个数极大
6. 所有顶点度的和必须为偶数

有向图：

1. 回路或环：第一个顶点和最后一个顶点相同的路径。
2. 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
3. 连通：顶点 v 至 v’之间有路径存在
4. 强连通图：有向图 G 的任意两点之间都是连通的，则称 G 是强连通图。各个顶点间均可达。
5. 强连通分量：极大连通子图

6. 有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第 V 行中的 1 的个数是 V 的出度

7. 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。

8. 完全图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。必定是连通图。
9. 有向完全图：有 n(n-1) 条边的有向图。其中 n 是结点个数。每两个顶点之间都有两条方向相反的边连接的图。

10. 一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：

    E

    >=

    V

    -1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：

    E

    >=

    V

    ，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：

    E

    =

    V

    -1。

图的存储形式

1. 邻接矩阵和加权邻接矩阵

   • 无权有向图：出度: i 行之和；入度: j 列之和。
   • 无权无向图：i 结点的度: i 行或 i 列之和。
   • 加权邻接矩阵：相连为 w，不相连为∞

2. 邻接表

   • 用顶点数组表、边（弧）表表示该有向图或无向图
   • 顶点数组表：用数组存放所有的顶点。数组大小为图顶点数 n
   • 边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。
   • n 个顶点的无向图的邻接表最多有 n(n-1) 个边表结点。有 n 个顶点的无向图最多有 n(n-1)/2 条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有 n(n-1) 个结点

图的遍历

深度优先搜索利用栈，广度优先搜索利用队列

求一条从顶点 i 到顶点 s 的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时, BFS 算法可用来解决单源最短路径问题。

生成树和最小生成树

每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有 DFS 生成树和 BFS 生成树。

生成树是连通图的极小子图，有 n 个顶点的连通图的生成树必定有 n-1 条边, 在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图

最小生成树：生成树中边的权值 (代价) 之和最小的树。最小生成树问题是构造连通网的最小代价生成树。

Kruskal 算法：令最小生成树集合 T 初始状态为空，在有 n 个顶点的图中选取代价最小的边并从图中删去。若该边加到 T 中有回路则丢弃，否则留在 T 中；依此类推，直至 T 中有 n-1 条边为止。

Prim 算法、Kruskal 算法和 Dijkstra 算法均属于贪心算法。

1. Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
2. Dijkstra 算法解决了从某个原点到其余各顶点的最短路径问题，由循环嵌套可知该算法的时间复杂度为 O(NN)。若要求任一顶点到其余所有顶点的最短路径，一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上，再来一次循环，此时整个算法的复杂度就变成了 O(NN*N)。
3. Bellman-Ford 算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。该算法返回一个布尔值，以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。

双连通图和关节点

若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。

没有关节点的连通图为双连通图

1. 若生成树的根结点，有两个或两个以上的分支，则此顶点 (生成树的根) 必为关节点；
2. 对生成树上的任意一个非叶 “顶点”，若其某棵子树中的所有“顶点” 没有和其祖先相通的回边，则该 “顶点” 必为关节点。

有向无环图及其应用

拓扑排序。在用邻接表表示图时, 对有 n 个顶点和 e 条弧的有向图而言时间复杂度为 O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。

AOV 网 (Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为 AOV 网。AOV 网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑有序序列：把 AOV 网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若 v_i 是 v_j 前驱，则 v_i 一定在 v_j 之前；对于没有优先关系的点，顺序任意。

拓扑排序：对 AOV 网络中顶点构造拓扑有序序列的过程。方法：

1. 在有向图中选一个没有前驱的顶点且输出之
2. 从图中删除该顶点和所有以它为尾的弧
3. 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止 (此时说明图中有环）

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环 (回路). 深度优先搜索只要在其中记录下搜索的节点数 n，当 n 大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。

算法描述：

1. 把邻接表中入度为 0 的顶点依此进栈

2. 若栈不空，则

   • 栈顶元素 v_j 退栈并输出；
   • 在邻接表中查找 v_j 的直接后继 v_k，把 v_k 的入度减 1；若 v_k 的入度为 0 则进栈
3. 若栈空时输出的顶点个数不是 n，则有向图有环；否则，拓扑排序完毕。

AOE 网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

一些定义：

1. 事件的最早发生时间（ve(j)）：从源点到 j 结点的最长的路径。意味着事件最早能够发生的时间。
2. 事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件 j 必须发生的时间。
3. 活动 a_i 由弧