数据结构

图G是由一个非空的顶点集合V和一个描述顶点之间的关系即边集E的一种数据结构，记为G = (V，E)

1、图G不可以为空，E可以为空，但V一定是非空集

2、图分为无向图和有向图

① 无向图：若E为无向边的有限集合，则G为无向图。

边是顶点的无序对，记为 ( v 1 ， v 2 ) (v_1，v_2) (v1​，v2​)或 ( v 2 ， v 1 ) (v_2，v_1) (v2​，v1​)，且 ( v 1 ， v 2 ) = ( v 2 ， v 1 ) (v_1，v_2) = (v_2，v_1) (v1​，v2​)=(v2​，v1​)，v1和v2互为邻接点

G可以表示为：

G = (V，E)​

V = {A，B，C，D，E}

E = {(A，B)，(B，D)，(B，E)，(C，D)，(C，E)}

如图：

② 有向图：若E为有向边(也称弧)的有限集合，则G为有向图。

弧是顶点的有序对，记为 < v i , v j > ，其中 v i v_i vi​是弧尾， v j v_j vj​是弧头

G可以表示为：

G = (V，E)​

V = {A，B，C，D，E}

E = {，，，，，，，}

如图：

1、顶点的度、入度、出度

① 无向图：顶点的度是指该顶点拥有的边数，记为TD(v)

如上图中：TD(A) = 1，TD(B) = 3，TD© = 2，TD(D) = 2，TD(E) = 2

对于无向图而言，有： ∑ i = 1 n T D ( v i ) = 2 ∣ E ∣ \displaystyle \sum^{n}_{i=1}{TD(v_i)} = 2|E| i=1∑n​TD(vi​)=2∣E∣

② 有向图：入度是以该顶点为终点的有向边的数目，记为ID(v)，出度是以该顶点为起点的有向边的数目，记为OD(v)

顶点v的度等于入度和出度之和，即TD(v) = ID(v) + OD(v)

如上图中：

ID(A) = 1，OD(A) = 4，TD(A) = 5

ID(B) = 1，OD(B) = 3，TD(B) = 4

ID© = 2，OD© = 1，TD© = 3

ID(D) = 2，OD(D) = 0，TD(D) = 2

ID(E) = 2，OD(E) = 0，TD(E) = 2

对于有向图而言，有： ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = ∣ E ∣ \displaystyle \sum^{n}_{i=1}{ID(v_i)}=\displaystyle \sum^{n}_{i=1}{OD(v_i)} = |E| i=1∑n​ID(vi​)=i=1∑n​OD(vi​)=∣E∣

2、路径

顶点 v i v_i vi​到 v j v_j vj​之间的一条路径是指顶点序列， v i , v 1 , v 2 , v 3 . . . v j v_i,v_1,v_2,v_3...v_j vi​,v1​,v2​,v3​...vj​

3、回路

第一个顶点和最后一个顶点相同的路径称为回路或环

4、简单路径

在路径序列中，顶点不重复出现的路径称为简单路径

5、简单回路

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

6、路径长度

路径上边的数目

7、连通图

无向图中，若从顶点 v i v_i vi​到顶点 v j v_j vj​有路径存在，则称 v i v_i vi​和 v j v_j vj​是连通的，任意两个顶点都是连通的图称为连通图

对于n个顶点的无向图G：

若G为连通图，则最少有n-1条边

若G为非连通图，则最多可能有 C n − 1 2 C_{n-1}^2 Cn−12​条边

8、强连通图

有向图中，若从顶点 v i v_i vi​到顶点 v j v_j vj​和从顶点 v j v_j vj​到顶点 v i v_i vi​都有路径存在，则称 v i v_i vi​和 v j v_j vj​是强连通的，任意两个顶点都是强连通的图称为强连通图

对于n个顶点有向图G：

若G为强连通图，则最少有n条边(形成回路)

9、子图

设有两个图G1 = (V1，E1)和G2 = (V2，E2)，若V2是V1的子集，且E2是E1的子集，则称G2是G1的子图

若G2中包含G1的所有顶点(可以不包含所有的边)，则称G2为G1的生成子图

10、连通分量

无向图中的极大连通子图称为连通分量

如图：

11、强连通分量

有向图中的极大强连通子图称为有向图的强连通分量

如图：

12、生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图

如图：

生成树是不唯一的

若顶点数为n，则生成树含有n-1条边

对于生成树，去掉一条边，则会变成非连通图，加上一条边则会形成一个回路

13、权

边的权：在一个图中，每条边都可以标上具有某种含义的数值，称为该边的权值

带权图/网：边上带有权值的图称为带权图或者网

带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

14、特殊图

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

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

若无向图顶点数 ∣ V ∣ = n |V| = n ∣V∣=n，则 ∣ E ∣ ∈ [ 0 , C n 2 ] = [ 0 , n ( n − 1 ) 2 ] |E|\in[0,C^2_n]=[0,\frac{n(n-1)}{2}] ∣E∣∈[0,Cn2​]=[0,2n(n−1)​]

若有向图顶点数 ∣ V ∣ = n |V| = n ∣V∣=n，则 ∣ E ∣ ∈ [ 0 , 2 C n 2 ] = [ 0 , n ( n − 1 ) ] |E|\in[0,2C^2_n]=[0,n(n-1)] ∣E∣∈[0,2Cn2​]=[0,n(n−1)]

邻接矩阵法是表示顶点之间相邻关系的矩阵

如下图：

图的广度优先搜索(Breadth-First-Search)类似于树的层序遍历

1、假设从图中某顶点 ｖ 出发，在访问了 ｖ 之后依次访问 ｖ 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问的顶点的邻接点” 先于“后被访问的顶点的邻接点” 被访问，直至图中所有已被访问的顶点的邻接点都被访问到

2、若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上 述过程，直至图中所有顶点都被访问到为止3、换句话说，广度优先搜索遍历图的过程中以 ｖ 为起始点，由近至远依次访问和 ｖ 有路径相通且路径长度为 1，2，… 的顶点， 广度优先遍历也需要用到标志数组 vis[N] 以避免重复访问，还需要用到队列来存放已经访问过的各相邻顶点

同一个图的邻接矩阵表示方式唯一，BFS遍历序列唯一

同一个图的邻接表表示方式不唯一，BFS遍历序列不唯一