图

存储结构

应用

操作：遍历

逻辑结构

定义

由顶点的有穷非空集合V(G)和顶点之间边的集合E(G)组成的网状数据结构

用|V|表示图中顶点个数，也是图的阶；|E|表示图中边的条数

基础分类

有向图

有向边的有限集合，<x,y>表示顶点x到y的一条弧，x为弧尾，y为弧头

无向图

无向边的有限集合，边表示为(x,y)

完全图

无向完全图

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

有向完全图

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

子图

G=(V,E)和G'=(V',E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图

顶点的度

有向图

无向图

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

出度

以该顶点为起点的有向边的数目

入度

以该顶点为终点的有向边的数目

权与网

每条边上标上的某种含义的数值为权值

边上带有权值的图称为网

路径和回路

一条路径是顶点v到e之间的一个顶点序列

路径长度等于路径上边的数目

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

简单路径

简单回路

连通

连通图

连通分量

顶点不重复出现的路径

除头尾顶点外，其余顶点不重复出现的回路

无向图中的极大连通子图

任意两个顶点都是连通的

强连通

定义

有向图中v到w和w到v之间都有路径

定义

无向图中两个顶点之间有路径

强连通图

图中任意一对顶点都是强连通的

强连通分量

有向图中极大强连通子图

生成树

定义

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

特点

砍去一条边，则会变成非连通图

加上一条边则会形成一个回路

生成森林

非连通图中连通分量的生成树的集合

邻接矩阵

定义

用两个数组表示图，一个一维数组存储顶点信息，一个二维数组储存边或者弧的信息

特点

无向图

一定是对称矩阵，且主对角线上全零

矩阵第i行非零元素的个数正好是第i个顶点的度

有向图

主对角线全零，不一定对称

vi顶点的入度为第i列各数之和，出度为第i行各数之和

带权图的邻接矩阵中对应项应存放权值

优点

容易确定图中任意两个顶点之间是否相连

稠密图适合用邻接矩阵表示，节省空间

缺点

确定有多少条边时，花费时间代价大

邻接表

稀疏图浪费大量空间

定义

由顶点表和边表组成，边表：对每个顶点建立单链表，第i个单链表中的结点表示依附于顶点vi的边(有向图则是以vi为尾的弧) ；顶点表：边表的头指针和顶点的数据信息顺序存储

特点

无向图

存储空间O(|V|+2|E|)

顶点的度为对应单链表上结点的个数

有向图

存储空间O(|V|+|E|)

出度为单链表上结点的个数，入度则需要搜索所有单链表

网图可以在边表结点定义中增加一个weight

优点

稀疏图极大节省存储空间

给定顶点容易找出其所有邻边

缺点

判断给定两个顶点之间是否存在边效率较低

有向图算入度需要遍历全表效率很低

深度优先遍历DFS

基本思想

从图中某个顶点V0出发，首先访问V0

依次从V0的未被访问的邻接点出发DFS，直到图中所有和V0有路径相通的顶点都被访问

实现方式

存储结构

用邻接矩阵

时间复杂度:O(n^2)

用邻接表

时间复杂度:O(n+e)

算法

递归

非递归

空间复杂度O(n)

广度优先遍历BFS

基本思想

从图中某个顶点V0出发，首先访问V0

依次访问V0的各个未被访问的邻接点

若Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问邻接点之前访问

实现方式

存储方式

用邻接表

时间复杂度:O(n+e)

用邻接矩阵

时间复杂度:O(n^2)

都需借助一个辅助队列Q，空间复杂度空间复杂度O(n)

最小生成树

最短路径

拓补排序

关键路径

定义

带权连通无向图的边的权值最小的生成树

性质

假设G=(V,E)时一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树

应用

普里姆Prim算法

克鲁斯卡尔Kruskal算法

定义

非网图

两顶点之间经过边数最少的路径

网图

两顶点经过的边上权值之和最少的路径

应用

迪杰斯特拉Dijkstra算法

弗洛伊德Floyd算法

定义

AOV网

拓补序列

顶点表示活动，弧表示优先关系的有向无环图

有向图G=(V,E)中V中顶点的线性序列

拓补排序

由AOV网构造拓补序列的过程

算法

1.从AOV网中选择一个没有前驱的顶点并输出

2.从网中删除该顶点和所有以它为起点的有向边

3.重复1和2直到当前AOV网为空或当前网中不存在无前驱的顶点为止

时间复杂度：O(n+e)

定义

AOE网

顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销的带权有向图

关键路径

从入度为零的顶点导出度为零的顶点的最长路径

关键活动

关键路径上的活动

算法

1.从源点出发，令ve=0，按拓补排序求其余顶点最早发生事件

2.从汇点出发，令vl=0，按逆拓补排序求其余顶点的最迟发生时间

3.根据各顶点的ve值求所有弧的最早开始时间

4.根据各顶点的vl值求所有弧的最迟开始时间

求AOE网中所有活动的差额d，找出d=0的活动构成关键路径