图的逻辑结构

图是由顶点及顶点间的关系(边)两个集合组成的数据结构，记作G=(V , E)。

V：顶点的集合 E：边的集合

顶点间是多对多的关系

例：如下图中有顶点： v1，v2，v3，v4，v5

图：graph 顶点：vertex 边：edge

有向图：图中每一条边都是有方向的 有向边记为： <vi,vj> 有向边，又称作：弧

例：该图有边

<v1,v2>,<v1,v3>,<v1,v5>

<v2,v4>,<v3,v1>,<v3,v2>

<v4,v1>

无向图：图中每一条边都是无方向的 无向边记为： (vi,vj)

例：该图有边

(v1,v2),(v1,v3),(v2,v3)

(v1,v4),(v1,v5)

有向图中：

顶点的度：与该顶点相连的边的个数 入度：以该顶点为终点的边数 出度：以该顶点为起点的边数

顶点的度 = 入度 + 出度

无向图中： 顶点的度：与该顶点相连的边的个数

图的分类

对于图G有V个顶点E条边

稀疏图：边的条数E远小于V²的图称为稀疏图

稠密图：边的条数E接近V²的图称为稠密图

路径

路径的长度：路径上边的数目

简单路径：一条路径的顶点序列中的顶点各不相同

例：

v3,v2,v4,v1 路径长度：3，是简单路径

v3,v1,v2,v4,v1 路径长度：4，不是简单路径

某路径的顶点序列为v1,v2...vn若v1=vn则该路称径为：回路或环

除第一个顶点和最后一个顶点相同外，其余顶点均不同，则称该回路为简单回路。

例：v1,v2,v4,v1 是简单回路

子图：图的部分顶点和边构成的图

连通性

无向图的连通性：图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通的。

无向图中任意两个顶点之间都能够连通，则称此图为连通图。

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

有向图中，若任意两个顶点 vi和 vj，满足从 vi 到 vj 以及从 vj 到 vi 都连通，则称此有向图为强连通图。

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

有向图中，若任意两个顶点 vi 和 vj，满足从 vi 到 vj 或从 vj 到 vi 连通，则称此有向图为单向连通图。

将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

强连通图、连通图、单向连通图三者之间的关系：

强连通图必然是单向连通图， 单向连通图必然是弱连通图， 反之未必。

图的存储邻接矩阵

设二维数组g, 若存在边(vi,vj)或<vi,vj>，则g[i][j] = 1，否则，g[i][j] = 0

邻接矩阵的空间复杂度：O(V^2)

邻接矩阵适合表示稠密图。

邻接表

头结点数组：存储每个边链表第一个结点的地址

边链表：单链表中每个结点表示依附于该顶点的一条边

邻接表的空间复杂度：O(V+E)

邻接表适合表示稀疏图。

邻接表 vector数组

vector<int> h[N];//h[i]：顶点i的邻接点们int n;//顶点总数//无向图添加边(a,b)h[a].push_back(b);h[b].push_back(a);//有向图添加弧<a,b>h[a].push_back(b);

对图G=(V, E)进行深度优先遍历与广度优先遍历的时间复杂度为：

如果使用邻接矩阵：O(V^2)

如果使用邻接表：O(V+E)