图由顶点集V和边集E组成，记为G=（V，E），使用V（G）表示所有顶点的集合（不能为空）；使用E（G）表示各个顶点之间的关系（可以为空）。若用V={v1,v2,v3,....,vn}来表示图，则使用|V|表示图中顶点的个数，使用E={（vi，vj）|vi∈V，vj∈V}，用|E|表示图中边的条数。

        若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为,其中v、w均为顶点，v成为弧尾，w称为弧头（分不清的话可以记想象一下拉弓的场景，如下图，顶点4的左半边可以看作弓，右边箭头可以想象成箭矢，头是我们，做的动作是拉弓射箭，尾是目标，也就是方向，即为箭头所指。），也称从v到w的弧，也称v邻接w（和是不相同的）。

 如上图，该有向图可以定义为G；

G=（V，E）

V={1，2，3，4}

E={,,,,}

若E是无向边（简称边）的有限集合，则图为无向边，边是顶点的无序对。记为（v,w）或（w，v）（相当于（v，w）和（w，v）等价）。可以说w和v互为邻接点。边（v，w）依附于w和v，或称边（v，w）和v，w相关联。如下图：

 如上图，该无向图可以描述为：

G=（V，E）

V={1，2，3，4}

E={（1，2），（1，3），（1，4），（2，3），（2，4），（3，4）}

简单图的要求：

①不存在重复边

②不存在顶点到自身的边

考研408数据结构仅讨论简单图：

无向图+边（|E|）的取值为（0到n（n-1）/2）=无向完全图

无向完全图在任意两个顶点之间都存在边

有向图+边（|E|）的取值为（0到n（n-1））=有向完全图

有向完全图任意两个顶点之间都存在两条方向相反的弧

1.两个图G=（E，V） G1=（E1，V1）

①若E1是E的子集，

②V1是V的子集，

则G1是G的子图。

2.若子图G1满足

V（G1）=V（G）（即子图中的顶点和总图的顶点完全相同）则称G1为G的

生成子图。

如下图，有向图G的子图为G1，生成子图为G2 

（1）连通的定义：从某一点V到某一点W有路径存在，则称V到W是连通的。

（2）连通图：如图中任意两个顶点都是连通的，则称该图为连通图。否则，则成为非连通图（换句话说，只要有一个点不是和其余的点连通的就是非连通图）。

（3）连通图：设顶点个数为n，则最少n-1条边，最多n（n-1）/2（无向图）

（4）非连通图：设顶点个数为n，若边数少于n-1，则该图为非连通图

（5）连通分量：无向图中的极大连通子图称为连通分量（连通分量是指无向图中的一个最大连通子图。也就是说，在一个无向图中，如果两个节点之间有路径相连，则这两个节点属于同一个连通分量。如果一个无向图中有多个连通分量，那么这个无向图就是非连通的。每个连通分量也被称为一个连通块。）

注意：极大连通子图是无向图的连通分量，而极小连通子图是无向图的生成树。极大连通子图要求子图尽可能地包含无向图的所有的边，而极小连通子图在保证具有所有顶点的情况下尽可能地减少边的条数。

（6）Question：连通分量和极大连通子图什么关系？

        Answer：

        连通分量是指无向图中的一组顶点（不只是两个），其中任意两个顶点都是连通的。极大连通子图是指无向图中的一个连通子图，它不能再添加更多的顶点或边而仍然保持连通性。

        因此，一个无向图的连通分量是由若干个极大连通子图组成的。每个极大连通子图都是一个连通分量，但一个连通分量不一定是极大连通子图。

（1）强连通图：强连通图指的是一个有向图中，任意两个顶点之间都是互相可连通的，也就是说，对于有向图中的任意两个点 u 和 v，都存在一条从 u 到 v 的有向路径和一条从 v 到 u 的有向路径。强连通图可以被看作是一个整体，其中的任意两个顶点是“相互可达”的。在强连通图中，不存在孤立的点或者点集。

（2）强连通分量：强连通分量是指在一个有向图中，若存在一些顶点集合，其中任意两个顶点都可以互相到达，则称这个集合为一个强连通分量。强连通分量可以理解为是图中的一个子图，其中所有顶点可以相互抵达。强连通分量是图论中一个重要的概念，常用于网络分析、路径规划等领域。

（3）Question：强连通图和强连通分量之间有什么关系？

Answer：

强连通图是指有向图中每一对顶点之间都存在一条有向路径，这意味着强连通图中任意两个顶点都能够相互到达。

强连通分量是在有向图中定义的，是指一个有向图中的极大强连通子图。

因此，一个强连通图就是一个只有一个强连通分量的有向图。而一个有向图可能会由多个强连通分量组成。

总之，强连通图是强连通分量的特殊情况。

无向图的生成树：

无向图的生成树是指通过从无向图中选择一些边形成的一棵包含所有节点的无向树。

无向图的生成森林：

无向图的生成森林是指通过从无向图中选择一些边形成的若干棵树，每棵树都包含该连通分量的所有节点。

无论是生成树还是生成森林，都要满足以下两个条件：

生成树或生成森林的边数必须等于节点数减1。

生成树或生成森林中不能存在环，即不能形成回路。

顶点的度：依附于该顶点的边的条数

入度：箭头指向该点的边的条数

出度：从该点出发的边的条数

TD（total degree）顶点的总度数=ID（in degree）入度+OD（out degree）出度

在所有的顶点中：总入度=总出度=图的边数

总度数=2*图的边数=总入度+总出度

在一个图中，每条边上都标上具有特定含义的数值，该数值就叫该边的权值。如果所有的边上都有权值，像这样的图就叫做带权图，也叫做网。

稠密图和稀疏图是相对模糊的概念，稠密图是边比较多的图，稀疏图是边比较少的图。一般的若图满足|E|（边的条数）