图

1.图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：
G=(V，E)
其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。
2.注意：在图中，顶点个数不能为零，但可以没有边。
3.无向边：若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。
4.无向图：图中的边都是无向边
5.有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>
6.有向图：如果图的任意两个顶点之间的边都是有向边，则称该图为有向图
7.简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现
8.邻接、依附：无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj
9.无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
10.有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图
11.稀疏图：称边数很少的图为稀疏图；
12.稠密图：称边数很多的图为稠密图。
13.顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。
14.顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；
15.顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。
16.权：是指对边赋予的有意义的数值量。
17.网：边上带权的图，也称网图。
18.路径：在无向图G=(V, E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<vij-1,vij>∈E。
19.路径长度：非带权图——路径上边的个数，带权图——路径上各边的权之和
20.回路（环）：第一个顶点和最后一个顶点相同的路径。
21.简单路径：序列中顶点不重复出现的路径。
22.简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
23.子图：若图G=（V，E），G’=（V’，E’），如果V’V 且E’  E ，则称图G’是G的子图。
24.连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。
25.连通分量：非连通图的极大连通子图称为连通分量。
26.强连通图：在有向图中，对图中任意一对顶点vi和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。
27.强连通分量：非强连通图的极大强连通子图。
28.生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。
29.生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。
30.图的遍历：深度优先搜索，广度优先搜索（标记已搜）
31.邻接矩阵存储：
用一个一维数组存储图中顶点的信息
用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。
32.邻接表存储参照我的另一篇博客：https://blog.****.net/weixin_43244265/article/details/90454560
33.十字链表：

34.十字链表节点结构：

35.生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。
36.最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。
37.最小生成树性质：假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u, v)的最小生成树。
38.最小生成树参照博客：https://blog.****.net/weixin_43244265/article/details/99644922（额(⊙﹏⊙)，还是忍不住打广告。。。）
39.最短路：在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。
40.Dijkstra算法：
基本思想：
设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，
对vi∈V-S，假设从源点v到vi的有向边为最短路径（从v到其余顶点的最短路径的初值）。
以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。
重复上述过程，直到集合V中全部顶点加入到集合S中。
41.路径长度最短的最短路径（即第一条最短路）的特点： 在这条路径上，必定只含一条边，并且这条边上的权值最小。
42.下一条路径长度次短的最短路径的特点：它只可能有两种情况：
或者是直接从源点到该点(只含一条边)；
或者是从源点经过顶点v1（第一条最短路径所依附的顶点），再到达该顶点(由两条边组成)。
43.再下一条路径长度次短的最短路径的特点: 它可能有四种情况：或者是直接从源点到该点(只含一条边)； 或者从源点经过顶点v1，再到达该顶点(由两条边组成)；或者是从源点经过顶点v2，再到达该顶点（两条条边）；或者是从源点经过顶点v1、v2，再到达该顶点（多条边）。
44.其余最短路径的特点： 它或者是直接从源点到该点(只含一条边)； 或者是从源点经过已求得最短路径的顶点（集合S中的顶点），再到达该顶点。
45. 弗罗伊德算法的基本思想如下：
设图g用邻接矩阵法表示，
求图g中任意一对顶点vi、 vj间的最短路径。
（-1） 将vi到vj 的最短的路径长度初始化为(vi,vj)， 然后进行如下n次比较和修正：
（0） 在vi、vj间加入顶点v0，比较（vi, v0, vj）和(vi, vj)的路径的长度，取其中较短的路径作为vi到vj的且中间顶点号不大于0的最短路径。
46.AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。
47.AOV网特点：
1.AOV网中的弧表示活动之间存在的某种制约关系。
2.AOV网中不能出现回路 。
48.拓扑序列：
设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点的拓扑序列中顶点vi必在顶点vj之前。
49.拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。
50.拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。
51.拓扑排序：
⑴ 从AOV网中选择一个没有前驱的顶点并且输出；
⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；
⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。
52.关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
53.关键活动：关键路径上的活动称为关键活动。